题意：一共4个点，从2出发，回到2，求大于等于k的最短路
思路：如果存在回到2的路径为k的路，那k+2w的路径一定存在，那只要求d[2][p]的最短路，p为路径长%2w。把这些值加2w加到超过k，取最小值。
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; const int maxn = 60005; int dis[5][5],w,inq[5][maxn]; ll d[5][maxn]; struct data { int p,wei; }; void spfa() { queue<data> q; while(!q.empty()) q.pop(); memset(inq,0,sizeof inq); memset(d,0x3f,sizeof d); d[2][0] = 0; q.push((data){2,0}); while(!q.empty()) { int x = q.front().p; int we = q.front().wei; q.pop(); inq[x][we] = 0; for(int i = -1; i <= 1; i += 2) { int y = (x+4+i) % 4; if(y == 0) y = 4; ll z = d[x][we] + dis[x][y]; if(d[y][z%w] > z) { d[y][z%w] = z; if(!inq[y][z%w]) { inq[y][z%w] = 1; q.push((data){y,z%w}); } } } } } int main(void) { int T,a,b,c,e; ll k; scanf("%d",&T); while(T--) { scanf("%lld%d%d%d%d",&k,&a,&b,&c,&e); dis[1][2] = dis[2][1] = a; dis[2][3] = dis[3][2] = b; dis[3][4] = dis[4][3] = c; dis[4][1] = dis[1][4] = e; w = 2 * min(dis[1][2],dis[2][3]); spfa(); ll ans = 0x3f3f3f3f3f3f3f3f; for(int i = 0; i < w; i++) { ll temp = k - d[2][i]; if(temp <= 0) ans = min(ans,d[2][i]); else ans = min(ans,d[2][i] + (temp/w) * w + ( (temp%w)?1:0 ) * w ); } printf("%lld\n",ans); } return 0; }
