给你一个4个点的环，问你从2号点出发， 再回到2号点，长度>=K的最短路是多少。
#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define LL long long #define fi first #define se second #define mem(a,b) memset((a),(b),sizeof(a)) const int MAXN=4+3; const int MAXM=60000+3; struct Node { int p; LL dis; Node(int p, LL d):p(p), dis(d){} }; LL K, G[MAXN][MAXN], m, ans; bool vis[MAXN][MAXM]; LL dist[MAXN][MAXM];//从1开始到达i，模m等于j的最短路 void spfa(int s) { queue<Node> que; mem(vis, 0); mem(dist, 0x3f); que.push(Node(1, 0)); dist[1][0]=0; vis[1][0]=true; while(!que.empty()) { int u=que.front().p; LL now_dis=que.front().dis; vis[u][now_dis%m]=false; que.pop(); for(int i=-1;i<2;i+=2) { int v=(u+i+4)%4; LL next_dis=now_dis+G[u][v], next_m=next_dis%m; if(v==s)//形成环，更行答案 { if(next_dis<K) ans=min(ans, next_dis+((K-next_dis-1)/m+1)*m); else ans=min(ans, next_dis); } if(dist[v][next_m]>next_dis) { dist[v][next_m]=next_dis; if(!vis[v][next_m]) { que.push(Node(v, next_dis)); vis[v][next_m]=true; } } } } } int main() { int T_T; scanf("%d", &T_T); while(T_T--) { scanf("%lld", &K); for(int i=0;i<4;++i) { scanf("%lld", &G[i][(i+1)%4]); G[(i+1)%4][i]=G[i][(i+1)%4]; } m=2*min(G[1][0], G[1][2]);//最小环 ans=((K-1)/m+1)*m;//只使用最短的回路 spfa(1); printf("%lld\n", ans); } return 0; }