【HDOJ6071】Lazy Running(同余最短路思想)

传送门

• 题目：
  四个点$1,2,3,4$顺序连成环，给定相邻两点间的距离，问从$2$号点出发再回到$2$号点的所有路径中，路径长度不小于$k$的最小值。输出这个最小值。$1\le k\le 1e18$
• 思路：
  主要用到同余的思想。
  记$w=min(di{s}_{12},di{s}_{23})$对于$2\to 2$的一条路径，记其路径长度为$len$，那么$len+k\ast 2w$，$(k\ge 0)$对应的路径也是一种合法路径，这些合法路径长度根据$\%2w$的值将其分为$2w$组，并且求出每个同余类$i$对应的最短的合法路径的长度$mlen[i]$。
  $mlen[i]$表示从$2\to 2$的合法路径中（路径长度为len），满足$len\%(2w)=i$的最小的$len$值。
  对于每个同余类$i$，如果$mlen[i]\ge k$那么更新答案，否则，在$mlen[i]$的基础上累加$2w$，直至满足长度$\ge k$，再更新答案。
  那么怎么获得$mlen[]$数组呢，可以暴搜，也可以用spfa做。
  用spfa做的话$dis[i][j]$表示从$2$出发到达$i$满足$\%(2w)=j$的最小长度。队列里存上一个点距离当前点的最短距离，初始化存入{$2,0$}。
• ac代码：

#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 6e4+10;
struct Edge{
int nxt; ll val;
};
struct node{
int now; ll v;
};
vector<Edge> edge[5];
queue<node> q;
int t;
ll d12, d23, d34, d41, w, k, dis[5][maxn];
void spfa()
{
for(int i = 0; i <= 4; i++)
for(int j = 0; j < w; j++)
dis[i][j] = LLONG_MAX;
q.push({2, 0});
while(!q.empty())
{
int now = q.front().now; ll v = q.front().v; q.pop();
for(auto e: edge[now])
{
ll tmp = v+e.val;
if(dis[e.nxt][tmp%w]>tmp)
{
dis[e.nxt][tmp%w] = tmp;
q.push({e.nxt, tmp});
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld %lld %lld %lld", &k, &d12, &d23, &d34, &d41);
w = 2*min(d12, d23);
edge[1].push_back({2, d12}); edge[2].push_back({1, d12});
edge[2].push_back({3, d23}); edge[3].push_back({2, d23});
edge[3].push_back({4, d34}); edge[4].push_back({3, d34});
edge[4].push_back({1, d41}); edge[1].push_back({4, d41});
spfa();
ll ans = LLONG_MAX;
for(int i = 0; i < w; i++)
{
if(dis[2][i]>=k) ans = min(ans, dis[2][i]);
else
{
ll sub = k-dis[2][i];
ll p = sub%w==0 ? sub : (sub/w+1)*w;
ans = min(ans, dis[2][i]+p);
}
}
printf("%lldn", ans);
for(int i = 1; i <= 4; i++) edge[i].clear();
}
return 0;
}

最后

以上就是曾经电话为你收集整理的【HDOJ6071】Lazy Running(同余最短路思想)的全部内容，希望文章能够帮你解决【HDOJ6071】Lazy Running(同余最短路思想)所遇到的程序开发问题。

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