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