← 返回题目列表

AtCoder · awc0077_d

D. 蓬松的云跳跃

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

有 N 天空中飘浮着蓬松的云朵,编号从 1 to N。有 M 云间的风路,每条风路都可以双向穿越。

各云 i 具有蓬松度 F_i (介于 1 和 K,包括)。每个云的蓬松程度是一个固定值,并且在整个游戏过程中不会改变。

风路 j 连接云 U_j 和云 V_j,并且有基本行程时间 T_j.

高桥从云开始 1 旨在实现云 N 遵循风路。他可能多次穿过同一片云或同一风路。

高桥有一种称为“当前蓬松度”的状态,其初始值为 F_1,云的蓬松程度 1。当高桥穿越风路时 j 当前蓬松度为 f,所需时间为 T_j \times f。越蓬松,遇到风的阻力就越大,行进的时间就越长。

高桥每次到云 i 通过风路,他可以选择采用蓬松程度 F_i 将到达的云作为他的“当前蓬松度级别”,或者不执行任何操作并保持他当前的蓬松度级别。每次他到达同一个云时都可以做出这个选择。选择后的“当前蓬松度”用于计算穿过下一个风路时的成本。

求高桥从云端旅行的最短总时间 1 到云 N。若云 N 无法到达,输出 -1.

约束

  • 2 \leq N \leq 100000
  • 0 \leq M \leq 100000
  • 1 \leq K \leq 5
  • 1 \leq F_i \leq K (1 \leq i \leq N)
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 可能有多个风路连接同一对云
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • 所有输入值均为整数
  • 保证答案最多是 10^{18} (可到达时)

输入

N M K
F_1 F_2 \ldots F_N
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
  • 第一行包含云的数量 N,风路数 M,以及最大蓬松度水平 K,用空格分隔。
  • 第二行包含蓬松度级别 每个云的 F_1, F_2, \ldots, F_N ,用空格分隔。
  • 以下 M 线给出了风路的信息。的 (2 + j)第行包含云数 U_j, V_j 由 j第风程,以及基本行程时间 T_j,用空格分隔。

输出

一行输出高桥从云端旅行的最短总时间 1 到云 N。若云 N 无法到达,输出 -1.


示例输入 1

4 4 3
2 1 3 1
1 2 5
2 4 4
1 3 2
3 4 1

示例输出 1

6

示例输入 2

5 3 3
1 2 3 1 2
1 2 10
2 3 5
4 5 7

示例输出 2

-1

示例输入 3

8 12 5
4 2 5 1 3 2 1 4
1 2 3
1 3 2
2 4 6
3 4 1
4 5 7
5 8 2
4 6 3
6 7 4
7 8 5
2 6 10
3 5 4
1 2 8

示例输出 3

19

示例输入 4

20 30 5
5 4 3 2 1 5 1 2 3 4 5 1 2 3 4 5 1 2 3 1
1 2 100
1 3 7
2 4 6
3 4 2
4 5 10
5 6 3
6 20 50
3 7 8
7 8 1
8 9 1
9 10 1
10 20 20
5 11 4
11 12 4
12 13 4
13 14 4
14 20 4
2 15 30
15 16 2
16 17 2
17 18 2
18 19 2
19 20 2
7 12 9
8 13 9
9 14 9
10 15 9
11 16 9
4 18 25
1 20 1000

示例输出 4

74

示例输入 5

2 1 1
1 1
1 2 1000000000

示例输出 5

1000000000