分数: 500 点
问题陈述
有 N 城镇编号 1,\ldots,N 和 M 道路编号 1,\ldots,M.
路 i 连接城镇 A_i 和 B_i。 当您使用道路时,您的 分数 $$$v$$$ 的 更改如下:
- 当您从城镇搬出时 A_i 到镇 B_i 使用道路 i,您的分数增加 C_i;当你离开城镇时 B_i 到镇 A_i 使用道路 i,您的分数减少了 C_i.
您的分数可能会变成负数。
回答以下问题 Q 问题。
- 如果您从城镇开始旅行 X_i 初始分数 0,找到当你在城镇时可能获得的最高分数 Y_i.
在这里,如果您无法从城镇前往 X_i 到镇 Y_i,打印nan代替;当你在城里时,如果你能得到尽可能多的分数 问题陈述中指定的 Y_i,打印inf。
约束
- 2\leq N \leq 10^5
- 0\leq M \leq 10^5
- 1\leq Q \leq 10^5
- 1\leq A_i,B_i,X_i,Y_i \leq N
- 0\leq C_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q A_1 B_1 C_1 \vdots A_M B_M C_M X_1 Y_1 \vdots X_Q Y_Q
输出
打印 Q 行。
的 i- 第行应包含以下问题的答案 i- 第一个问题。
示例输入 1
5 5 3 1 2 1 1 2 2 3 4 1 4 5 1 3 5 2 5 3 1 2 3 1
示例输出 1
-2 inf nan
对于第一个问题,如果您使用道路 5 从城镇搬出 5 到镇 3,即可获得分数 -2 当你在城里时 3.
由于你无法将分数调大,所以答案是 -2.
第二个问题,当你在城里时,你想要多大的分数都可以 2 如果您的出行方式如下: 反复“使用道路” 2 从城镇搬出 1 到镇 2 然后使用道路 1 从城镇搬出 2 到镇 1“只要你想要多少次, 最后使用道路 2 从城镇搬出 1 到镇 2.
对于第三个问题,你无法从城镇到达 3 到镇 1.
示例输入 2
2 1 1 1 1 1 1 1
示例输出 2
inf
道路的端点可能相同,问题中给出的端点也可能相同。
示例输入 3
9 7 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9
示例输出 3
inf nan nan inf -9