102617: [AtCoder]ABC261 Ex - Game on Graph

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$.

问题描述

我们有一个有$N$个顶点和$M$条边的有向图。第$i$条边从顶点$A_i$指向顶点$B_i$，权重为$C_i$。

最初，棋子在顶点$v$上。Takahashi和Aoki将轮流移动棋子，如下所示：

• 如果没有从棋子所在顶点出发的边，结束游戏。
• 如果从棋子所在顶点出发有边，选择其中一条边，并沿着这条边移动棋子。

Takahashi先走。Takahashi试图使棋子经过的边的权重总和最小，而Aoki试图使其最大化。
更正式地说，他们的目标如下。
Takahashi优先考虑在有限步内结束游戏。如果可能，他试图使棋子经过的边的权重总和最小。
Aoki优先考虑防止游戏在有限步内结束。如果不可能，他试图使棋子经过的边的权重总和最大。
（如果棋子多次经过同一条边，权重将相应地增加多次。）

确定当双方都玩得最优时，游戏是否在有限步内结束。如果结束，找出棋子经过的边的权重总和。

约束条件

• $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$
• 没有多条边。即，$(A_i,B_i)\neq(A_j,B_j)$对于$i\neq 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$

输出

如果双方都玩得最优时，游戏不会在有限步内结束，输出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

首先，Takahashi将棋子移动到顶点$3$。接下来，Aoki将棋子移动到顶点$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$。