概述
题不是很难但是解法感觉很妙，就写一发题解
题意就是一个正方形的图，每条边有边权，求从点2出发再回到点2的路中大于等于K的最小值
K<=1e18,d<=3e4
令w=min(d12,d32)
如果存在回到2长度为x的方案，那么一定存在长度为x+2w的方案
即对于任意x，如果存在这样的方案就可以给x不断加2w直到大于等于K
而且对于x<y且x%2w=y%2w的情况，x必然比y优
于是对于∀j∈[0,2w),求出到达2的路径长度模2w为j的最小值
于是把每个点拆成2w个以后跑最短路就可以了
注意如果dis(2,j)>K的话就不能往上补2w了
最后
以上就是怡然鸡翅为你收集整理的[HDU6071][2017多校第四场][Lazy Running]的全部内容，希望文章能够帮你解决[HDU6071][2017多校第四场][Lazy Running]所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![2017多校联合赛1[题解]](/uploads/reation/bcimg7.png)
![[HDU6071][2017多校第四场][Lazy Running]](/uploads/reation/bcimg11.png)
发表评论 取消回复