#P17854. [Ontak2019]PIZ
[Ontak2019]PIZ
— 披萨外送博弈
一座城市有 栋房屋和 条双向道路,道路有正长度,任意两栋房屋互相可达,没有自环和重边。两兄弟分别在房屋 、 开披萨店,房屋 能带来收益 ,这个收益可以为负。
两人进行如下游戏,由第一位兄弟先手,之后轮流行动。每人的配送半径最初都是 ,所有房屋最初都没有归属。
轮到某人时,他必须增大自己的配送半径。所有尚未归属任何人、且到他的店的最短路距离不超过新半径的房屋,都会永久归他所有。本次行动必须至少获得一栋此前没有归属的房屋;已经归对方的房屋不会被抢走。
所有房屋都有归属时游戏结束。每人的最终收益等于归他的房屋的 之和。两人都希望最大化自己的最终收益。
求双方均采用最优策略时,各自的最终收益。两家店所在的房屋本身也参与争夺,其收益保证为0。
输入格式
第一行两个整数 。
第二行两个不同的整数 ,表示先手和后手的店的位置。
第三行 个整数 。
接下来 行,每行三个整数 ,表示道路的两个端点及长度。
输出格式
输出两个整数,依次表示先手和后手的最优最终收益。
数据范围
,,,。
,;。保证图连通、无自环及重边。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 20 | |
| 2 | 40 | |
| 3 | 无 |
样例 1
输入:
4 3
1 2
0 0 1 -1
1 3 1
2 3 1
3 4 1
输出:
0 0