D - Fluffy Cloud Hopping Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

空に N 個のもこもこした雲が浮かんでおり、 1 から N までの番号が付けられています。雲の間には M 本の風の通り道があり、それぞれ双方向に移動することができます。

各雲 i にはもこもこ度 F_i（ 1 以上 K 以下の整数）が定められています。雲のもこもこ度は固定値であり、ゲームを通じて変化しません。

風の通り道 j は雲 U_j と雲 V_j を結び、基本移動時間 T_j を持ちます。

高橋君は雲 1 からスタートし、風の通り道をたどって雲 N に到達することを目指します。同じ雲や同じ風の通り道を複数回通ることもできます。

高橋君には「現在のもこもこ度」という状態があり、初期値は雲 1 のもこもこ度 F_1 です。高橋君が現在のもこもこ度 f の状態で風の通り道 j を通るとき、かかる時間は 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
  • 1 行目には、雲の数 N 、風の通り道の数 M 、もこもこ度の最大値 K が、スペース区切りで与えられる。
  • 2 行目には、各雲のもこもこ度 F_1, F_2, \ldots, F_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、風の通り道の情報が与えられる。 2 + j 行目には、 j 番目の風の通り道が結ぶ雲の番号 U_j , V_j と、基本移動時間 T_j が、スペース区切りで与えられる。

出力

高橋君が雲 1 から雲 N まで移動するのにかかる合計時間の最小値を 1 行で出力せよ。雲 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

Score : 400 pts

Problem Statement

There are N fluffy clouds floating in the sky, numbered from 1 to N. There are M wind paths between the clouds, each of which can be traversed in both directions.

Each cloud i has a fluffiness level F_i (an integer between 1 and K, inclusive). The fluffiness level of each cloud is a fixed value and does not change throughout the game.

Wind path j connects cloud U_j and cloud V_j, and has a base travel time T_j.

Takahashi starts at cloud 1 and aims to reach cloud N by following wind paths. He may pass through the same cloud or the same wind path multiple times.

Takahashi has a state called "current fluffiness level," whose initial value is F_1, the fluffiness level of cloud 1. When Takahashi traverses wind path j with a current fluffiness level of f, the time it takes is T_j \times f. The fluffier he is, the more wind resistance he encounters, and the longer the travel takes.

Each time Takahashi arrives at a cloud i via a wind path, he can choose either to adopt the fluffiness level F_i of the arrived cloud as his "current fluffiness level," or to do nothing and keep his current fluffiness level. This choice can be made each time he arrives at the same cloud. The "current fluffiness level" after this choice is used for the cost calculation when traversing the next wind path.

Find the minimum total time for Takahashi to travel from cloud 1 to cloud N. If cloud N cannot be reached, output -1.

Constraints

  • 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)
  • There may be multiple wind paths connecting the same pair of clouds
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers
  • It is guaranteed that the answer is at most 10^{18} (when reachable)

Input

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
  • The first line contains the number of clouds N, the number of wind paths M, and the maximum fluffiness level K, separated by spaces.
  • The second line contains the fluffiness levels F_1, F_2, \ldots, F_N of each cloud, separated by spaces.
  • The following M lines give the information of the wind paths. The (2 + j)-th line contains the cloud numbers U_j, V_j connected by the j-th wind path, and the base travel time T_j, separated by spaces.

Output

Output in one line the minimum total time for Takahashi to travel from cloud 1 to cloud N. If cloud N cannot be reached, output -1.

Sample Input 1

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

Sample Output 1

6

Sample Input 2

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

Sample Output 2

-1

Sample Input 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

Sample Output 3

19

Sample Input 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

Sample Output 4

74

Sample Input 5

2 1 1
1 1
1 2 1000000000

Sample Output 5

1000000000