Skip to content

LibreOJ - 2759. 飞天鼠

题解约 1.6 千字
# S2OJ # LibreOJ # 图论 # 2014 # JOI # 最短路 # Dijkstra
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

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

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

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

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

#输入格式

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

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

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

对于任意 1≤j<k≤M1\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 分 N≤1000N\le 1000
M≤3000M\le 3000
Hi≤100H_{i}\le 100
Tj≤100T_{j}\le 100		 无
2 25 分 2≤N≤1000002\le N\le 100000
1≤M≤3000001\le M\le 300000
1≤Hi≤1091\le H_i\le 10^9
1≤Tj≤1091\le T_j\le 10^{9}		 X=0X=0
3 50 分 2≤N≤1000002\le N\le 100000
1≤M≤3000001\le M\le 300000
1≤Hi≤1091\le H_i\le 10^9
1≤Tj≤1091\le T_j\le 10^9		 无

表格中的 Hi,TjH_i, T_j 满足：1≤i≤N,1≤j≤M1\le i\le N, 1\le j\le M。

所有数据满足 0≤X≤H10\le X\le H_1。

#思路

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

对于每条边，会有以下几种情况：

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

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

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}