atcoder#ABC280F. [ABC280F] Pay or Receive

[ABC280F] Pay or Receive

配点 : 500500

問題文

1,,N1,\ldots,N の番号がついた NN 個の街と、1,,M1,\ldots,M の番号がついた MM 本の道路があります。

道路 ii は街 AiA_iBiB_i を結んでいます。道路を通行すると、所持している ポイント が次の通り増減します。

  • 道路 ii を使って、街 AiA_i から街 BiB_i に移動するときにはポイントが CiC_i 増加し、街 BiB_i から街 AiA_i に移動するときにはポイントが CiC_i 減少する。

所持しているポイントは負にもなりえます。

次の QQ 個の質問に答えてください。

  • 所持しているポイントが 00 である状態で街 XiX_i から移動を始めたとき、街 YiY_i にいる状態で所持しているポイントの最大値を出力せよ。 ただし、街 XiX_i から街 YiY_i に到達できないときは nan、街 YiY_i にいる状態で所持しているポイントをいくらでも増やせるときは inf を代わりに出力せよ。

制約

  • 2N1052\leq N \leq 10^5
  • 0M1050\leq M \leq 10^5
  • 1Q1051\leq Q \leq 10^5
  • 1Ai,Bi,Xi,YiN1\leq A_i,B_i,X_i,Y_i \leq N
  • 0Ci1090\leq C_i \leq 10^9
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

NN MM QQ

A1A_1 B1B_1 C1C_1

\vdots

AMA_M BMB_M CMC_M

X1X_1 Y1Y_1

\vdots

XQX_Q YQY_Q

出力

問題文の指示通りに QQ 行出力せよ。 ii 行目には ii 番目の質問に対する答えを出力せよ。

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

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

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

33 番目の質問では、街 33 から移動を始めて街 11 へ到達することはできません。

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