Skip to content

LibreOJ - 2759. 飞天鼠

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

本题有多个提交渠道:


题面

题目描述

译自 JOI 2014 Final T4「フクロモモンガ

飞天鼠 JOI 君住着的森林里长着编号为 11NNNN 棵桉树。第 ii 棵树的高度是 HiH_{i} 米。

JOI 君能在其中的 MM 对桉树之间直接飞行,在各对树木之间飞行所需的时间是固定的。当 JOI 君在树木之间飞行的时候,他离地面的高度会每秒下降 11 米。也就是说,如果 JOI 君现在离地高度是 hh 米,在树木之间飞行需要 tt 秒,那么飞行之后的离地高度就会变成 hth-t 米。当 hth-t 小于 00 或大于目标树木的高度时则不能飞行。

JOI 君还能沿着树的侧面上下移动,使得他的离地高度在 00 到当前所在树木高度的范围内变化。JOI 君每使自己的离地高度增加或减少 11 米都需要 11 秒的时间。

JOI 君要从 11 号树木上高度为 XX 米的位置出发,到树木 NN 的顶端(高度为 HNH_{N} 米的位置)去。他想知道为了达成这个目标所需时间的最小值。

给出各棵树木的高度、JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度,请求出到达树木 NN 顶端所需时间的最小值。

输入格式

第一行包含三个以空格分开的整数 N,MN, MXX,意义分别与题目描述中的 N,MN, MXX 相同。

接下来 NN 行中,第 i(1iN)i(1\le i\le N) 行有一个整数 HiH_{i},表示树木ii的高度是 HiH_{i} 米。

接下来 MM 行中,第 j(1jM)j(1\le j\le M) 行有三个以空格分开的整数 Aj,Bj,TjA_{j},B_{j},T_{j} (1Aj,BjN,(1\le A_{j}, B_{j}\le N, AjBj)A_{j}\ne B_{j}),表示 IOI 君能花 TjT_{j} 秒的时间从 AjA_{j} 飞到 BjB_{j} 或从 BjB_{j} 飞到 AjA_{j}

对于任意 1j<kM1\le j < k\le M,满足 (Aj,Bj)(Ak,Bk)(A_{j},B_{j})\neq (A_{k},B_{k})(Aj,Bj)(Bk,Ak)(A_{j},B_{j})\neq (B_{k},A_{k})

输出格式

输出到标准输出,仅一行一个整数,表示从树木 11 上高度为 XX 米处移动到树木 NN 顶端所需时间的最小值(单位:秒)。如果不能到达目的地则输出 1-1

输入输出样例

样例输入 #1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

样例输出 #1

110

样例解释 #1

下列是其中一种最优解:

  1. 沿着树木 11 向上爬 5050 米。
  2. 从树木 11 飞到树木 22
  3. 从树木 22 飞到树木 44
  4. 从树木 44 飞到树木 55
  5. 沿着树木 55 向上爬 1010 米。

样例输入 #2

2 1 0
1
1
1 2 100

样例输出 #2

-1

样例输出 #2

JOI 君无法从树木 11 飞到树木 22

样例输入 #3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

样例输出 #3

100

数据范围与约定

本题采用 Subtask 方式评测。

子任务编号 分值 数据范围 特殊性质
1 25 分 N1000N\le 1000
M3000M\le 3000
Hi100H_{i}\le 100
Tj100T_{j}\le 100
2 25 分 2N1000002\le N\le 100000
1M3000001\le M\le 300000
1Hi1091\le H_i\le 10^9
1Tj1091\le T_j\le 10^{9}
X=0X=0
3 50 分 2N1000002\le N\le 100000
1M3000001\le M\le 300000
1Hi1091\le H_i\le 10^9
1Tj1091\le T_j\le 10^9

表格中的 Hi,TjH_i, T_j 满足:1iN,1jM1\le i\le N, 1\le j\le M

所有数据满足 0XH10\le X\le H_1

思路

可以使用最短路算法解决本题。

对于每条边,会有以下几种情况:

  1. 到达点的高度大于树顶高度。
    需要先向下爬到高度为 hv+wh_v + w 的点才能从该边飞过,可以证明这是最优选择。
  2. 在飞行途中落地。
    这种情况又细分为两种情况:
    1. 从树顶开始飞行时,无法到达终点。
      此种情况在加边时即可判定并丢弃这条边。
    2. 从树上某点开始飞行时,无法到达终点。
      处理完上一种情况以后,树上一定存在一个高度,使得从该高度开始正好可以飞到下一个点的 00 米高处。
      容易证明,先下降到高度为 ww 的点再飞过该边是最优选择。
  3. 能正常飞到终点。
    正常计算即可。

本题答案大小可能会超出 int 上界,因此需要使用 long long 存储。

代码

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

const int N = 100005;

int n, m, x, h[N], nh[N];
std::vector<std::pair<int, long long>> g[N];

// Dijkstra - Shortest Path
long long dist[N];
bool vis[N];
void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> q;
    q.push(std::make_pair(0, 1));
    nh[1] = x;
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : g[u]) {
            int v = e.first;
            long long w = e.second;
            if (nh[u] - w > h[v]) {  // 到达点的高度大于树顶高度
                if (dist[v] > dist[u] + nh[u] - h[v]) {
                    dist[v] = dist[u] + nh[u] - h[v];
                    nh[v] = h[v];
                    q.push(std::make_pair(dist[v], v));
                }
            } else if (nh[u] - w < 0) {  // 飞行中途会落地
                if (dist[v] > dist[u] + w - (nh[u] - w)) {
                    dist[v] = dist[u] + w - (nh[u] - w);
                    nh[v] = 0;
                    q.push(std::make_pair(dist[v], v));
                }
            } else if (dist[v] > dist[u] + w) {  // 其他情况
                dist[v] = dist[u] + w;
                nh[v] = nh[u] - w;
                q.push(std::make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;

        // 保证飞行中途不落地
        if (w <= h[u]) g[u].push_back(std::make_pair(v, w));
        if (w <= h[v]) g[v].push_back(std::make_pair(u, w));
    }
    dijkstra();
    cout << (dist[n] == 0x3f3f3f3f3f3f3f3f ? -1 : dist[n] + h[n] - nh[n]) << endl;
    return 0;
}