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("%I64dn", ans);
}
return 0;
}

最后

以上就是安静眼睛为你收集整理的HDU6071Lazy Running（同余最短路）的全部内容，希望文章能够帮你解决HDU6071Lazy Running（同余最短路）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。