Pay or Receive

题目描述

有 $N$ 个城镇，编号为 $1,\ldots,N$，以及 $M$ 条道路，编号为 $1,\ldots,M$。 道路 $i$ 连接城镇 $A_i$ 和 $B_i$。当你使用一条道路时，你的 分数 会按如下方式变化：

当你沿道路 $i$ 从城镇 $A_i$ 移动到城镇 $B_i$ 时，你的分数增加 $C_i$；当你沿道路 $i$ 从城镇 $B_i$ 移动到城镇 $A_i$ 时，你的分数减少 $C_i$。

你的分数可以为负数。 回答接下来 $Q$ 个问题。

如果你从城镇 $X_i$ 出发，初始分数为 $0$，求当你位于城镇 $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$ 个问题的答案。

5 5 3
1 2 1
1 2 2
3 4 1
4 5 1
3 5 2
5 3
1 2
3 1

-2
inf
nan

2 1 1
1 1 1
1 1

inf

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

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$ 输入中的所有数均为整数。对于第一个问题，如果你使用道路 $5$ 从城镇 $5$ 移动到城镇 $3$，当你到达城镇 $3$ 时可以得到分数 $-2$。
因为无法使分数更大，答案为 $-2$。 对于第二个问题，如果你反复按如下方式行走，就可以在到达城镇 $2$ 时使分数任意大： 重复“使用道路 $2$ 从城镇 $1$ 到城镇 $2$，然后使用道路 $1$ 从城镇 $2$ 到城镇 $1$”若干次， 最后再使用道路 $2$ 从城镇 $1$ 到城镇 $2$。 对于第三个问题，你无法从城镇 $3$ 到达城镇 $1$。
道路的端点可能相同，问题中给出的端点也可能相同。

标签: AtCoder|abc280F

来源

AtCoder|abc280F