Description 四个点1,2,3,4围成一个圈，给出12，23，34，41之间的距离，从2出发要求跑至少k米回到2处，问最短距离 Input 第一行一整数T表示用例组数，每组用例输入四个整数d1,d2,d3,d4分别表示12，23，34，41之间的距离(1<=T<=15,1<=k<=1e18,1<=d1,d2,d3,d4<=30000) Output 输出从2出发回到2的距离不少于k的最短距离 Sample Input 1 2000 600 650 535 380 Sample Output 2165 Solution 令m=2*min(d1,d2)，如果存在一个距离为x的方案则必然存在一个距离为x+m的方案（因为从2可以跑到1或3再跑回来），考虑四个点在模m意义下的最短路，dis[i][j]表示从2出发到i点距离模m为j的最短路长度，求出最短路后，枚举j，如果dis[2][j] < k则拿m把dis[2][j]补到不小于k为止，更新答案，如果dis[2][j]>=k则直接更新答案 Code
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int>P; const int maxn=60001; const ll INF=2e18; struct node { int v,mw; ll w; node(){}; node(int _v,int _mw,ll _w){v=_v,mw=_mw,w=_w;} }; queue<node>que; int T,d[4],mod; ll k,dis[4][maxn]; int main() { scanf("%d",&T); while(T--) { scanf("%I64d",&k); for(int i=0;i<4;i++)scanf("%d",&d[i]); mod=2*min(d[0],d[1]); for(int i=0;i<4;i++) for(int j=0;j<mod;j++) dis[i][j]=INF; while(!que.empty())que.pop(); que.push(node(1,0,0)); while(!que.empty()) { node now=que.front(); que.pop(); int v=now.v,mw=now.mw,tv,tmw; ll w=now.w,tw; if(dis[v][mw]<w)continue; tv=(v+1)%4,tmw=(mw+d[v])%mod,tw=w+d[v]; if(dis[tv][tmw]>tw)dis[tv][tmw]=tw,que.push(node(tv,tmw,tw)); tv=(v+3)%4,tmw=(mw+d[tv])%mod,tw=w+d[tv]; if(dis[tv][tmw]>tw)dis[tv][tmw]=tw,que.push(node(tv,tmw,tw)); } ll ans=INF; for(int i=0;i<mod;i++) if(dis[1][i]<k) { ll temp=(k-dis[1][i]+mod-1)/mod*mod+dis[1][i]; ans=min(ans,temp); } else ans=min(ans,dis[1][i]); printf("%I64d\n",ans); } return 0; }