F - Pay or Receive Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1,\ldots,N の番号がついた N 個の街と、1,\ldots,M の番号がついた 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 を代わりに出力せよ。

制約

  • 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

1 番目の質問では、道路 5 を使って街 5 から街 3 に移動すると、ポイントを -2 所持している状態で街 3 にいることができます。
これ以上ポイントを大きくすることはできないので答えは -2 になります。

2 番目の質問では、「道路 2 を使って街 1 から街 2 に移動し、道路 1 を使って街 2 から街 1 に移動する」 という行動を好きなだけ繰り返したあと、道路 2 を使って街 1 から街 2 に移動することで、 街 2 にいる状態で所持しているポイントをいくらでも増やすことができます。

3 番目の質問では、街 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

Score : 500 points

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