← 返回题目列表

AtCoder · abc280_f

I. 支付或接收

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

分数: 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