E - Flights 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1400 点

問題文

日本には N 個の空港があり、それぞれに 1, 2, \dots, N と番号が付けられています。AtCoder 航空は、日本で M 本の航空路線を運航しており、それぞれに 1, 2, \dots, M と番号が付けられています。航空路線 j は空港 A_j を出発し空港 B_j に到着するものであり、価格は C_j \times F 円です。

AtCoder 航空で飛行機に乗ると「マイル」という通貨を得ることができます。最初の時点では 0 マイル持っています。航空路線 j に一回乗ると C_j マイルを得ます。また、空港 i では 1 マイル当たり R_i 円に換金することができます。なお、制約 0 \leq R_i \leq F-1 より、飛行機を乗り継いで無制限にお金を得ることはできません。

ここで、換金するマイルや所持金は整数にならなくてもかまいませんが、マイルや所持金が負の数になってはいけません。

さて、空港 1 から空港 N に飛行機で行くために、最初に何円以上持っている必要があるでしょうか？

\mathrm{TESTCASES} 個のテストケースについて解いてください。

制約

  • 1 \leq \mathrm{TESTCASES} \leq 40\,000
  • 2 \leq N \leq 400
  • 1 \leq M \leq N \times (N-1)
  • 1 \leq F \leq 100
  • 1 \leq A_j \leq N
  • 1 \leq B_j \leq N
  • A_j \neq B_j
  • (A_1, B_1), (A_2, B_2), \dots, (A_M, B_M) はすべて異なる
  • 1 \leq C_j \leq 100
  • 0 \leq R_i \leq F-1
  • 空港 1 から空港 N に行く方法が存在する
  • すべてのテストケースに対する N^2 の総和は 160\,000 以下である
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。ここで、\mathrm{case}_k は k 番目のテストケースを意味します。

\mathrm{TESTCASES}
\mathrm{case}_1
\mathrm{case}_2
 \vdots
\mathrm{case}_{\mathrm{TESTCASES}}

各テストケースは、以下の形式で与えられます。

N M
F
A_1 B_1 C_1
A_2 B_2 C_2
 \vdots
A_M B_M C_M
R_1 R_2 \cdots R_N

出力

\mathrm{TESTCASES} 行出力してください。k 行目には、k 番目のテストケースについて、空港 1 から空港 N に飛行機で行くことが可能になるような最初の所持金の最小値を出力してください。

正解との絶対誤差または相対誤差が 10^{-6} 以下の場合、正答とみなされます。

入力例 1

1
3 2
10
1 2 7
2 3 9
2 2 2

出力例 1

146

最初に所持金を 146 円持っている場合、以下のようにして空港 1 から空港 3 に行くことができます。

  1. 航空路線 1 を使って、空港 1 から空港 2 に行く。所持金は 146 - 70 = 76 円になり、7 マイルを得る。
  2. 空港 2 で、7 マイルを 14 円に換金する。所持金は 76 + 14 = 90 円になる。
  3. 航空路線 2 を使って、空港 2 から空港 3 に行く。所持金は 90 - 90 = 0 円になり、9 マイルを得る。

最初の所持金が 146 円未満のとき、空港 1 から空港 3 に行くことはできません。

入力例 2

1
4 4
10
1 2 7
2 4 9
2 3 1
3 2 1
2 2 9 2

出力例 2

106

最初に 106 円持っている場合、以下のようにして空港 1 から空港 4 に行くことができます。

  1. 航空路線 1 を使って、空港 1 から空港 2 に行く。所持金は 106 - 70 = 36 円になり、7 マイルを得る。
  2. 航空路線 3 を使って、空港 2 から空港 3 に行く。所持金は 36 - 10 = 26 円になり、1 マイルを得る。
  3. 空港 3 で、8 マイルを 72 円に換金する。所持金は 26 + 72 = 98 円になる。
  4. 航空路線 4 を使って、空港 3 から空港 2 に行く。所持金は 98 - 10 = 88 円になり、1 マイルを得る。
  5. 空港 2 で、1 マイルを 2 円に換金する。所持金は 88 + 2 = 90 円になる。
  6. 航空路線 2 を使って、空港 2 から空港 4 に行く。所持金は 90 - 90 = 0 円になり、9 マイルを得る。

最初の所持金が 106 円未満のとき、空港 1 から空港 4 に行くことはできません。

入力例 3

1
7 8
100
3 2 81
3 4 42
1 6 97
4 5 42
4 1 59
6 3 34
5 3 68
2 7 47
0 58 37 10 89 16 0

出力例 3

16354.2758620689655172413793103448275862068965

Score : 1400 points

Problem Statement

Japan has N airports numbered 1, 2, \dots, N. AtCoder Airlines operates M directed flight routes in Japan, numbered 1, 2, \dots, M. Route j goes from airport A_j to airport B_j and costs C_j \times F yen.

Flying with AtCoder Airlines earns “miles.” You start with 0 miles. Taking route j once grants C_j miles. At airport i, you can exchange miles for money at the rate R_i yen per mile. Because of the constraint 0 \le R_i \le F-1, endless profit cycles are impossible.

You can exchange a non-integral amount of miles or have a non-integral amount of money, but you cannot have a negative amount of miles or money.

What is the minimum initial amount of money in yen needed to fly from airport 1 to airport N?

Solve \mathrm{TESTCASES} test cases.

Constraints

  • 1 \le \mathrm{TESTCASES} \le 40\,000
  • 2 \leq N \leq 400
  • 1 \leq M \leq N \times (N-1)
  • 1 \leq F \leq 100
  • 1 \leq A_j \leq N
  • 1 \leq B_j \leq N
  • A_j \neq B_j
  • (A_1, B_1), (A_2, B_2), \dots, (A_M, B_M) are all different.
  • 1 \le C_j \le 100
  • 0 \le R_i \le F-1
  • It is possible to go from airport 1 to airport N.
  • The sum of N^2 over all test cases is at most 160\,000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_k represents the k-th test case:

\mathrm{TESTCASES}
\mathrm{case}_1
\mathrm{case}_2
 \vdots
\mathrm{case}_{\mathrm{TESTCASES}}

Each test case is given in the following format:

N M
F
A_1 B_1 C_1
A_2 B_2 C_2
 \vdots
A_M B_M C_M
R_1 R_2 \cdots R_N

Output

Print \mathrm{TESTCASES} lines. The k-th line should contain the minimum initial amount of money in yen needed to fly from airport 1 to airport N for the k-th test case.

Your output is considered as correct if its absolute or relative error is at most 10^{-6}.

Sample Input 1

1
3 2
10
1 2 7
2 3 9
2 2 2

Sample Output 1

146

If you start with 146 yen, you can go from airport 1 to airport 3:

  1. Take route 1 to go from airport 1 to airport 2. You now have 146-70=76 yen, and get 7 miles.
  2. At airport 2, exchange 7 miles for 14 yen. You now have 76+14=90 yen.
  3. Take route 2 to go from airport 2 to airport 3. You now have 90-90=0 yen, and get 9 miles.

If you start with less than 146 yen, you cannot go to airport 3.

Sample Input 2

1
4 4
10
1 2 7
2 4 9
2 3 1
3 2 1
2 2 9 2

Sample Output 2

106

If you start with 106 yen, you can go from airport 1 to airport 4:

  1. Take route 1 to go from airport 1 to airport 2. You now have 106-70=36 yen, and get 7 miles.
  2. Take route 3 to go from airport 2 to airport 3. You now have 36-10=26 yen, and get 1 mile.
  3. At airport 3, exchange 8 miles for 72 yen. You now have 26+72=98 yen.
  4. Take route 4 to go from airport 3 to airport 2. You now have 98-10=88 yen, and get 1 mile.
  5. At airport 2, exchange 1 mile for 2 yen. You now have 88+2=90 yen.
  6. Take route 2 to go from airport 2 to airport 4. You now have 90-90=0 yen, and get 9 miles.

If you start with less than 106 yen, you cannot go to airport 4.

Sample Input 3

1
7 8
100
3 2 81
3 4 42
1 6 97
4 5 42
4 1 59
6 3 34
5 3 68
2 7 47
0 58 37 10 89 16 0

Sample Output 3

16354.2758620689655172413793103448275862068965