[ABC261Ex] Game on Graph

题意翻译

Takahashi 和 Aoki 正在一张 $n$ 个点,$m$ 条边的带权有向图上玩游戏。游戏规则如下: - 有一颗最初在 $s$ 点的棋子。双方轮流移动这颗棋子,Takahashi 先手。 - 每一次移动都可以使棋子从边的一端移动到另一端。如果无法移动,也就是不存在出边时,游戏结束。 - 定义一局游戏的得分为棋子移动路径上的边权之和。如果经过一条边多次,边权也计算多次。 Takahashi 想要最小化游戏的得分,但 Aoki 想要最大化得分。请输出在最优策略下游戏的最终得分。特别地,如果游戏无法结束,请输出 `INFINITY`。 $1\le n\le 2\times 10^5,\ 0\le m\le 2\times 10^5$。有向图保证没有重边和自环,但 **不保证无环**。

题目描述

[problemUrl]: https://atcoder.jp/contests/abc261/tasks/abc261_h $ N $ 頂点 $ M $ 辺の有向グラフがあります。辺 $ i $ は頂点 $ A_i $ から $ B_i $ への有向辺で、重みが $ C_i $ です。 最初、頂点 $ v $ に駒が置かれています。高橋君と青木君が交互に次のように駒を動かすゲームを行います。 - 駒が置かれている頂点から出る辺が存在しないとき、ゲームを終了する。 - 駒が置かれている頂点から出る辺が存在するとき、そのうちいずれかの辺を選び、選んだ辺に沿って駒を移動する。 ゲームは高橋君から始め、高橋君はゲームが終了するまでに通った辺の重みの和を小さくしようとし、青木君は大きくしようとします。 $ 2 $ 人が目指すものはより厳密には、次の通りです。 高橋君は、ゲームを有限回の操作で終了させることを最優先し、それが可能ならば、ゲームが終了するまでに通る辺の重みの和を小さくしようとします。 青木君は、ゲームを有限回の操作で終了させないことを最優先し、それが不可能ならば、ゲームが終了するまでに通る辺の重みの和を大きくしようとします。 (駒が同じ辺を複数回通った場合は、重みはその回数だけ加算されるものとします。) $ 2 $ 人が最善を尽くしたときゲームが有限回の操作で終了するか判定し、終了するならば、ゲームが終了するまでに通る辺の重みの和を求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ 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

输入样例 #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\ \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 $ - 入力に含まれる値は全て整数 ### Sample Explanation 1 まず高橋君は頂点 $ 3 $ に駒を動かし、次に青木君が頂点 $ 7 $ に駒を動かし、ゲームが終了します。 ゲームが終了するまでに通る辺の重みの和は $ 10+30=40 $ になります。 ### Sample Explanation 2 有限回の操作でゲームは終了しません。 ### Sample Explanation 3 $ 1\to\ 2\ \to\ 3\ \to\ 1\ \to\ 2\to\ 4 $ と駒は動かされます。