分数: 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.