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 存储。

#代码

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;
}