← 返回题目列表

AtCoder · abc261_h

Ex. 图上的游戏

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个有向图 N 顶点和 M 边缘。边缘 i 来自 Vertex A_i to B_i 的重量为 C_i.

最初,Vertex 上有一块 v。高桥和青木将玩一个游戏,他们轮流移动棋子,如下所示:

  • 如果没有从放置棋子的顶点出发的边,则结束游戏。
  • 如果存在从放置棋子的顶点出发的边,请选择其中一条边并沿该边移动棋子。

高桥先行。高桥试图最小化棋子所经过的边缘的总重量,而青木则试图最大化它。
更正式地说,他们的目标如下。
高桥优先考虑以有限步数结束游戏。如果可能的话,他会尝试最小化工件所经过的边缘的总重量。
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

首先,高桥将棋子移动到顶点 3。接下来,Aoki 会将棋子移至 Vertex 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.