分数: 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