HDU6071Lazy Running（同余最短路）

题意：

 给你一个由四个节点组成的环，求从节点2出发，回到节点2的不小于k的最短路。

思路：

取w=\min(d_{1,2},d_{2,3}) w=min(d​1,2​​,d​2,3​​)，那么对于每一种方案，均可以通过往返跑$w$这条边使得距离增加$2w$。也就是说，如果存在距离为$k$的方案，那么必然存在距离为$k+2w$的方案。

设dis_{i,j}dis​i,j​​表示从起点出发到达$i$，距离模$2w$为$j$时的最短路，那么根据dis_{2,j}dis​2,j​​解不等式即可得到最优路线。

时间复杂度$O(w\log w)$。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll k, m, ans, G[5][5], dist[5][60005]; bool vis[5][60005]; struct Node { int p; ll dis; Node(int p, ll dis):p(p), dis(dis){} }; void spfa(int s) { queue<Node> q; memset(vis, false, sizeof(vis)); memset(dist, 0x3f, sizeof(dist)); dist[s][0] = 0; vis[s][0] = true; q.push(Node(s, 0)); while(!q.empty()) { int u = q.front().p; ll now_dis = q.front().dis; vis[u][now_dis%m] = false; q.pop(); for(int i = -1; i <= 1; 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]) { vis[v][next_m] = true; q.push(Node(v, next_dis)); } } } } } int main() { int t; scanf("%d", &t); while(t--) { scanf("%I64d", &k); for(int i = 0; i < 4; i++) { scanf("%I64d", &G[i][(i+1)%4]); G[(i+1)%4][i] = G[i][(i+1)%4]; } m = 2* min(G[0][1], G[1][2]); ans = ((k-1)/m+1) * m; spfa(1); printf("%I64d\n", ans); } return 0; }