[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 $ と駒は動かされます。