腼腆草莓

文章
7
资源
0
加入时间
2年10月21天

HDU 6071 Lazy Running

题意:  给你一个由四个节点组成的环,求从节点2出发,回到节点2的不小于k的最短路。思路:取w=\min(d_{1,2},d_{2,3})w=min(d​1,2​​,d​2,3​​),那么对于每一种方案,均可以通过往返跑ww这条边使得距离增加2w2w。也就是说,如果存在距离为kk的方案,那么必然存在距离为k+2wk+2w的方案。设dis_{i,j}dis​i,j​​表示从起