分数: 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 前往机场 2。你现在有 146-70=76 日元,并得到 7 英里。
- 在机场 2, 交换 7 里程 14 日元。你现在有 76+14=90 日元。
- 采取路线 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 前往机场 2。你现在有 106-70=36 日元,并得到 7 英里。
- 采取路线 3 从机场出发 2 前往机场 3。你现在有 36-10=26 日元,并得到 1 英里。
- 在机场 3, 交换 8 里程 72 日元。你现在有 26+72=98 日元。
- 采取路线 4 从机场出发 3 前往机场 2。你现在有 98-10=88 日元,并得到 1 英里。
- 在机场 2, 交换 1 英里 2 日元。你现在有 88+2=90 日元。
- 采取路线 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