← 返回题目列表

AtCoder · agc072_e

E. 航班 2

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

分数: 1400 点

问题陈述

日本有 N 机场编号 1, 2, \dots, N。 AtCoder 航空公司运营 M 日本直飞航线,编号 1, 2, \dots, M。路线 j 从机场出发 A_j 前往机场 B_j 和成本 C_j \times F 日元。

搭乘 AtCoder Airlines 航班可赢取“里程”。你开始于 0 英里。采取路线 j 一旦授予 C_j 英里。在机场 i,您可以按照以下汇率将里程兑换成金钱 R_i 每英里日元。因为条件限制 0 \le R_i \le F-1,无限的利润循环是不可能的。

您可以兑换非整数的里程或拥有非整数的金钱,但不能拥有负数的里程或金钱。

从机场起飞所需的最低初始日元金额是多少 1 前往机场 N?

解决 \mathrm{TESTCASES} 测试用例。

约束

  • 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) 都是不同的。
  • 1 \le C_j \le 100
  • 0 \le R_i \le 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- 第行应包含从机场起飞所需的最低日元初始金额 1 前往机场 N 为 k- 第一个测试用例。

如果您的输出的绝对或相对误差最多为 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 日元,你不能去机场 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 日元,你不能去机场 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