#P17838. [ONTAK 2021]GRA
[ONTAK 2021]GRA
最大最小游戏
一个有向图的点 上写着正整数 。棋子最初在点 。Amelia 先手,两人轮流行动,每次可以沿一条出边移动棋子,也可以立即结束游戏。结束时棋子所在点的数值就是游戏结果。
Amelia 希望结果尽量大,Bazyli 希望结果尽量小。如果没有人提前结束,棋子移动恰好 次后自动结束,并以当时所在点的数值为结果。双方均采取最优策略,求最终结果。
输入格式
第一行 ,第二行 个数 。接下来 行,每行 ,表示有向边 。允许重复边,没有自环。
输出格式
输出最优博弈结果。
数据范围
,,,,。
样例
4 4
1 10 4 5
1 2
2 3
2 4
3 1
4