atcoder#ABC280F. [ABC280F] Pay or Receive

[ABC280F] Pay or Receive

题目描述

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

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

  • 道路 i i を使って、街 Ai A_i から街 Bi B_i に移動するときにはポイントが Ci C_i 増加し、街 Bi B_i から街 Ai A_i に移動するときにはポイントが Ci C_i 減少する。

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

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

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

输入格式

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

N N M M Q Q A1 A_1 B1 B_1 C1 C_1 \vdots AM A_M BM B_M CM C_M X1 X_1 Y1 Y_1 \vdots XQ X_Q YQ Y_Q

输出格式

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

题目大意

nn 个小镇,编号 11 ~ nn,还有 mm 条路,编号 11 ~ mm

ii 条路连接 Ai{A_i}Bi{B_i},当你走过一条路时,你的得分会遵循以下变化:

  • 当你用第 ii 条路从 Ai{A_i}Bi{B_i},你的得分增加 Ci{C_i} ; 当你用第 ii 条路从 Bi{B_i}Ai{A_i},你的得分减少 Ci{C_i}

你的得分可能为负数。

回答如下的 QQ 个问题:

  • 如果你从 Xi{X_i} 这个小镇出发(初始得分为 00 ), 求出你在 Yi{Y_i} 小镇时的最大得分。

  • 如果你不能从 Xi{X_i} 这个小镇出发到达 Yi{Y_i} 小镇,输出 nan

  • 如果你从 Xi{X_i} 这个小镇出发到达 Yi{Y_i} 小镇可以挣得无限的分数,输出 inf

输出格式:

输出遵循以下格式:

NN MM QQ

A1{A_1} B1{B_1} C1{C_1}

……

AM{A_M} BM{B_M} CM{C_M}

X1{X_1} Y1{Y_1}

……

XM{X_M} BM{B_M}

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 N  105 2\leq\ N\ \leq\ 10^5
  • 0 M  105 0\leq\ M\ \leq\ 10^5
  • 1 Q  105 1\leq\ Q\ \leq\ 10^5
  • 1 Ai,Bi,Xi,Yi  N 1\leq\ A_i,B_i,X_i,Y_i\ \leq\ N
  • 0 Ci  109 0\leq\ C_i\ \leq\ 10^9
  • 入力は全て整数である

Sample Explanation 1

1 1 番目の質問では、道路 5 5 を使って街 5 5 から街 3 3 に移動すると、ポイントを 2 -2 所持している状態で街 3 3 にいることができます。 これ以上ポイントを大きくすることはできないので答えは 2 -2 になります。 2 2 番目の質問では、「道路 2 2 を使って街 1 1 から街 2 2 に移動し、道路 1 1 を使って街 2 2 から街 1 1 に移動する」 という行動を好きなだけ繰り返したあと、道路 2 2 を使って街 1 1 から街 2 2 に移動することで、 街 2 2 にいる状態で所持しているポイントをいくらでも増やすことができます。 3 3 番目の質問では、街 3 3 から移動を始めて街 1 1 へ到達することはできません。

Sample Explanation 2

始点と終点が同じ街である道路や、始点と終点が同じ街である質問が含まれることもあります。