Score : $500$ points

问题描述

设有 $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。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ towns numbered $1,\ldots,N$ and $M$ roads numbered $1,\ldots,M$.

Road $i$ connects towns $A_i$ and $B_i$. When you use a road, your score changes as follows:

• when you move from town $A_i$ to town $B_i$ using road $i$, your score increases by $C_i$; when you move from town $B_i$ to town $A_i$ using road $i$, your score decreases by $C_i$.

Your score may become negative.

Answer the following $Q$ questions.

• If you start traveling from town $X_i$ with initial score $0$, find the maximum possible score when you are at town $Y_i$.
  Here, if you cannot get from town $X_i$ to town $Y_i$, print nan instead; if you can have as large a score as you want when you are at town $Y_i$, print inf instead.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines as specified in the Problem Statement.
The $i$-th line should contain the answer to the $i$-th question.

Sample Input 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

Sample Output 1

-2
inf
nan

For the first question, if you use road $5$ to move from town $5$ to town $3$, you can have a score $-2$ when you are at town $3$.
Since you cannot make the score larger, the answer is $-2$.

For the second question, you can have as large a score as you want when you are at town $2$ if you travel as follows: repeatedly "use road $2$ to move from town $1$ to town $2$ and then use road $1$ to move from town $2$ to town $1$" as many times as you want, and finally use road $2$ to move from town $1$ to town $2$.

For the third question, you cannot get from town $3$ to town $1$.

Sample Input 2

2 1 1
1 1 1
1 1

Sample Output 2

inf

The endpoints of a road may be the same, and so may the endpoints given in a question.

Sample Input 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

Sample Output 3

inf
nan
nan
inf
-9

update @ 2024/3/10 11:46:37