102805: [AtCoder]ABC280 F - Pay or Receive

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

问题描述

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

道路$i$连接城镇$A_i$和$B_i$。当你使用一条道路时，你的**分数**会发生如下变化：

• 当你从城镇$A_i$使用道路$i$移动到城镇$B_i$时，你的分数增加$C_i$；当你从城镇$B_i$使用道路$i$移动到城镇$A_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$，当你在城镇$3$时，你的分数可以是$-2$。
由于你不能使分数更大，所以答案是$-2$。

对于第二个问题，如果你按照以下方式旅行： 反复地“使用道路$2$从城镇$1$移动到城镇$2$，然后使用道路$1$从城镇$2$移动到城镇$1$”任意多次， 最后使用道路$2$从城镇$1$移动到城镇$2$。 你可以在城镇$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