AT_abc261_h [ABC261Ex] Game on Graph

题目描述

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

最初，棋子被放置在顶点 $v$ 上。高桥君和青木君轮流按如下规则移动棋子：

• 如果当前棋子所在的顶点没有出边，则游戏结束。
• 如果当前棋子所在的顶点有出边，则可以选择其中一条边，沿该边移动棋子。

游戏由高桥君先手。高桥君的目标是在有限步内结束游戏，并且尽量使经过的边权和最小；青木君的目标是尽量让游戏无法在有限步内结束，如果无法做到，则尽量使经过的边权和最大。 更严格地说，目标如下： 高桥君优先保证游戏能在有限步内结束，如果可以做到，则尽量使经过的边权和最小。 青木君优先保证游戏无法在有限步内结束，如果无法做到，则尽量使经过的边权和最大。 （如果棋子多次经过同一条边，则该边的权重会被多次累加。）

请判断当两人都采取最优策略时，游戏是否会在有限步内结束。如果会结束，请输出游戏过程中经过的边权和。

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

如果两人都采取最优策略时，游戏不会在有限步内结束，则输出 INFINITY。 如果会在有限步内结束，则输出游戏过程中经过的边权和。

输入输出样例 #1

输入 #1

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

输出 #1

40

输入输出样例 #2

输入 #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

输入 #3

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

输出 #3

5

说明/提示

限制条件

• $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$
• 输入中的所有值均为整数。

样例解释 1

首先高桥君将棋子移动到顶点 $3$，然后青木君将棋子移动到顶点 $7$，游戏结束。游戏过程中经过的边权和为 $10+30=40$。

样例解释 2

游戏不会在有限步内结束。

样例解释 3

棋子的移动顺序为 $1\to 2\to 3\to 1\to 2\to 4$。

由 ChatGPT 4.1 翻译