鏈接HDU 6071 Lazy Running
- 給出四個點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<bits/stdc++.h>
#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<ip>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]<Dis[to[k]][v]){Dis[to[k]][v]=Dis[i][b]+w[k];Q.push((ip){to[k],v,Dis[to[k]][v]});}}}
}void sol(){cnt=0;memset(hd,0,sizeof(hd));memset(nt,0,sizeof(nt));memset(to,0,sizeof(to));cin>>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<bas;++j)if(Dis[2][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;
}
)
