链接

• 给出四个点1，2，3，4，1和2，2和3，3和4，4和1之间有路相连，现在从2点出发，最后回到2点，要求路径大于等于\(K\)，问路径长度最短是多少，\(K\leq 10^{18},d\leq 3*10^4\)。
• 同余最短路套路了，取一条与\(2\)相连的权值最小的边\(w\)。
• 若存在一条从起点到终点的长度为k的路径，那么必然存在一条长度为\(k+2w\)的路径。
• 即只要一开始在那条边上往返走就好了。
• 设\(d_{i,j}\)表示从起点到\(i\)，路径长度模\(2w\)为\(j\)时，路径长度的最小值。
• 然后\(dij\)预处理\(d\)，最后枚举所有剩余系，如果大于等于\(K\)就恰好更新答案，否则补上剩下除以\(2*w\)向上取整数。

//HDU 6071 Lazy Running#include
    
     #define R register int#define ll long long using namespace std;const int N=100010;const int n=4;int t,u,bas,x,cnt,hd[N],to[N],nt[N],w[N],vis[10][N];ll K,ans,Dis[5][N];void link(R f,R t,R d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=d,hd[f]=cnt;}struct ip{int id,s;ll vl;};int operator < (ip x,ip y){return x.vl>y.vl;}priority_queue
     
      Q;int gi(){    R x=0,k=1;char c=getchar();    while((c<'0'||c>'9')&&c!='-')c=getchar();    if(c=='-')k=-1,c=getchar();    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();    return x*k;}void dij(){    memset(Dis,0x7f,sizeof(Dis));    memset(vis,0,sizeof(vis));    Dis[2][0]=0,Q.push((ip){2,0,0});    while(!Q.empty()){        R i=Q.top().id,b=Q.top().s;Q.pop();        if(vis[i][b])continue;vis[i][b]=1;        for(R k=hd[i];k;k=nt[k]){            R v=(b+w[k])%bas;            if(Dis[i][b]+w[k]
      
       >K,bas=2e9,ans=1e18;    u=gi(),link(1,2,u),link(2,1,u),bas=min(bas,u);    u=gi(),link(3,2,u),link(2,3,u),bas=min(bas,u);    u=gi(),link(3,4,u),link(4,3,u);    u=gi(),link(4,1,u),link(1,4,u);    bas*=2,dij();    for(R j=0;j
       
        =K)ans=min(ans,Dis[2][j]);        else ans=min(ans,Dis[2][j]+((K-Dis[2][j]+bas-1)/bas)*bas);    printf("%lld\n",ans);}int main(){    t=gi();while(t--)sol();    return 0;}