AT_abc280_f [ABC280F] Pay or Receive

题目描述

有 $N$ 个编号为 $1,\ldots,N$ 的城市，以及 $M$ 条编号为 $1,\ldots,M$ 的道路。

第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。通过道路时，所持有的“点数”会按如下方式增减：

• 如果使用第 $i$ 条道路从城市 $A_i$ 移动到城市 $B_i$，点数增加 $C_i$；如果从城市 $B_i$ 移动到城市 $A_i$，点数减少 $C_i$。

所持有的点数可以为负数。

请回答接下来的 $Q$ 个询问。

• 当你以点数为 $0$ 从城市 $X_i$ 出发时，抵达城市 $Y_i$ 时所能拥有的最大点数是多少？
  如果无法从城市 $X_i$ 到达城市 $Y_i$，请输出 nan；如果在城市 $Y_i$ 时点数可以无限增加，请输出 inf。

输入格式

输入按以下格式从标准输入给出。

$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

输入 #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

输入输出样例 #2

输入 #2

2 1 1
1 1 1
1 1

输出 #2

inf

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个询问，使用道路 $5$ 从城市 $5$ 移动到城市 $3$，可以在城市 $3$ 时拥有 $-2$ 的点数。无法再获得更大的点数，因此答案为 $-2$。
对于第 $2$ 个询问，可以“反复使用道路 $2$ 从城市 $1$ 到城市 $2$，再使用道路 $1$ 从城市 $2$ 回到城市 $1$”，然后再使用道路 $2$ 从城市 $1$ 到城市 $2$，这样可以让在城市 $2$ 时的点数无限增加。
对于第 $3$ 个询问，无法从城市 $3$ 出发到达城市 $1$。

样例解释 2

输入中可能包含起点和终点为同一城市的道路，或起点和终点为同一城市的询问。

由 ChatGPT 4.1 翻译