[HDU6071][2017多校第四场][Lazy Running]

228 阅读 0 评论 151 点赞

我是靠谱客的博主怡然鸡翅，这篇文章主要介绍[HDU6071][2017多校第四场][Lazy Running]，现在分享给大家，希望可以做个参考。

题不是很难但是解法感觉很妙，就写一发题解
题意就是一个正方形的图，每条边有边权，求从点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了