Ex - Game on Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の有向グラフがあります。辺 i は頂点 A_i から B_i への有向辺で、重みが C_i です。

最初、頂点 v に駒が置かれています。高橋君と青木君が交互に次のように駒を動かすゲームを行います。

  • 駒が置かれている頂点から出る辺が存在しないとき、ゲームを終了する。
  • 駒が置かれている頂点から出る辺が存在するとき、そのうちいずれかの辺を選び、選んだ辺に沿って駒を移動する。

ゲームは高橋君から始め、高橋君はゲームが終了するまでに通った辺の重みの和を小さくしようとし、青木君は大きくしようとします。
2 人が目指すものはより厳密には、次の通りです。
高橋君は、ゲームを有限回の操作で終了させることを最優先し、それが可能ならば、ゲームが終了するまでに通る辺の重みの和を小さくしようとします。
青木君は、ゲームを有限回の操作で終了させないことを最優先し、それが不可能ならば、ゲームが終了するまでに通る辺の重みの和を大きくしようとします。
（駒が同じ辺を複数回通った場合は、重みはその回数だけ加算されるものとします。）

2 人が最善を尽くしたときゲームが有限回の操作で終了するか判定し、終了するならば、ゲームが終了するまでに通る辺の重みの和を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1 \leq v \leq N
  • 1 \leq A_i,B_i \leq N
  • 多重辺は存在しない。すなわち i\neq j のとき (A_i,B_i)\neq(A_j,B_j)
  • 自己辺は存在しない。すなわち A_i\neq B_i
  • 0 \leq C_i \leq 10^9
  • 入力に含まれる値は全て整数

入力

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

N M v
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

2 人が最善を尽くしたとき、ゲームが有限回の操作で終了しないならば INFINITY と出力せよ。
有限回の操作で終了するならば、ゲームが終了するまでに通る辺の重みの和を出力せよ。

入力例 1

7 6 1
1 2 1
1 3 10
2 4 100
2 5 102
3 6 20
3 7 30

出力例 1

40

まず高橋君は頂点 3 に駒を動かし、次に青木君が頂点 7 に駒を動かし、ゲームが終了します。
ゲームが終了するまでに通る辺の重みの和は 10+30=40 になります。

入力例 2

3 6 3
1 2 1
2 1 2
2 3 3
3 2 4
3 1 5
1 3 6

出力例 2

INFINITY

有限回の操作でゲームは終了しません。

入力例 3

4 4 1
1 2 1
2 3 1
3 1 1
2 4 1

出力例 3

5

1\to 2 \to 3 \to 1 \to 2\to 4 と駒は動かされます。

Score : 600 points

Problem Statement

We have a directed graph with N vertices and M edges. Edge i is directed from Vertex A_i to B_i and has a weight of C_i.

Initially, there is a piece on Vertex v. Takahashi and Aoki will play a game where they alternate turns moving the piece as follows:

  • If there is no edge that goes from the vertex on which the piece is placed, end the game.
  • If there are edges that go from the vertex on which the piece is placed, choose one of those edges and move the piece along that edge.

Takahashi goes first. Takahashi tries to minimize the total weight of the edges traversed by the piece, and Aoki tries to maximize it.
More formally, their objectives are as follows.
Takahashi gives the first priority to ending the game in a finite number of moves. If this is possible, he tries to minimize the total weight of the edges traversed by the piece.
Aoki gives the first priority to preventing the game from ending in a finite number of moves. If this is impossible, he tries to maximize the total weight of the edges traversed by the piece.
(If the piece traverses the same edge multiple times, the weight is added that number of times.)

Determine whether the game ends in a finite number of moves when both players play optimally. If it ends, find the total weight of the edges traversed by the piece.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1 \leq v \leq N
  • 1 \leq A_i,B_i \leq N
  • There is no multi-edges. That is, (A_i,B_i)\neq(A_j,B_j) for i\neq j.
  • There is no self-loops. That is, A_i\neq B_i.
  • 0 \leq C_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M v
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

If the game does not end in a finite number of moves when both players play optimally, print INFINITY.
If the game ends in a finite number of moves, print the total weight of the edges traversed by the piece.

Sample Input 1

7 6 1
1 2 1
1 3 10
2 4 100
2 5 102
3 6 20
3 7 30

Sample Output 1

40

First, Takahashi will move the piece to Vertex 3. Next, Aoki will move the piece to Vertex 7, and the game will end.
The total weight of the edges traversed by the piece will be 10+30=40.

Sample Input 2

3 6 3
1 2 1
2 1 2
2 3 3
3 2 4
3 1 5
1 3 6

Sample Output 2

INFINITY

The game will not end in a finite number of moves.

Sample Input 3

4 4 1
1 2 1
2 3 1
3 1 1
2 4 1

Sample Output 3

5

The piece will go 1\to 2 \to 3 \to 1 \to 2\to 4.