题意大致就是 一张无向图 每条边可以多次经过 问s,到t 的不小于k的最短路 （或者仅仅等于k的最短路）
取m=2*min（s到下一个点的最短路径）: 如果一条路径长度sum可行 那么sum+m也是可行的
然后 dis[i][j]表示从起点s到i点 ，路径长度%m==j 的最短路径
最后就是利用同余的性质去跑最短路spfa
题目 HDU 6071
51NOD 1326
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <climits> #include <cmath> #include <vector> #include <set> #include <queue> #include <stack> #include <map> #include <sstream> #define LL long long #define fora(i,a,n) for(int i=a;i<=n;i++) #define fors(i,n,a) for(int i=n;i>=a;i--) #define sci(x) scanf("%d",&x) #define scl(x) scanf("%lld",&x) const int MAXN = 100024; const long long INF = 1e18 + 60002; const double eps = 1e-8; using namespace std; struct Node { LL v, mod, diss; Node(LL _v, LL _mod, LL _diss) { v = _v; mod = _mod; diss = _diss; } Node() {} }; LL t, k, m; LL g[4][60003]; bool vis[4][60003]; LL dis[4][4]; void spfa(LL v) { queue<Node>q; memset(vis, 0, sizeof(vis)); memset(g, 0x3f, sizeof(g)); q.push(Node(1, 0, 0)); vis[1][0] = 1; LL nex_dis, nex_mod, nex_v; while (!q.empty()) { Node f = q.front(); q.pop(); vis[f.v][f.mod] = 0; for (int i = -1, j = 0; j <= 1; i += 2, j++) { nex_v = (f.v + i + 4) % 4; nex_dis = f.diss + dis[f.v][nex_v]; nex_mod = nex_dis%m; if (g[nex_v][nex_mod]>nex_dis) { g[nex_v][nex_mod] = nex_dis; if(!vis[nex_v][nex_mod]){ vis[nex_v][nex_mod] = 1; q.push(Node(nex_v, nex_mod, nex_dis)); } } } } LL Min = 4*INF, num; for (int i = 0; i<m; i++) { num = g[1][i]; if (num<k) { num += ((k - num - 1) / m + 1)*m; } if (num<Min) Min = num; } printf("%lld\n", Min); } int main() { #ifdef local freopen("ini.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif scanf("%lld", &t); while (t--) { memset(dis, 0, sizeof(dis)); scanf("%lld", &k); for (int i = 0; i<4; i++) scanf("%lld", &dis[i][(i + 1) % 4]), dis[(i + 1) % 4][i] = dis[i][(i + 1) % 4]; m = 2 * min(dis[1][0], dis[1][2]); spfa(1); } return 0; }