HDU 6071 Lazy Running（模同余最短路）

Description
四个点1,2,3,4围成一个圈，给出12，23，34，41之间的距离，从2出发要求跑至少k米回到2处，问最短距离
Input
第一行一整数T表示用例组数，每组用例输入四个整数d1,d2,d3,d4分别表示12，23，34，41之间的距离(1<=T<=15,1<=k<=1e18,1<=d1,d2,d3,d4<=30000)
Output
输出从2出发回到2的距离不少于k的最短距离
Sample Input
1
2000 600 650 535 380
Sample Output
2165
Solution
令m=2*min(d1,d2)，如果存在一个距离为x的方案则必然存在一个距离为x+m的方案（因为从2可以跑到1或3再跑回来），考虑四个点在模m意义下的最短路，dis[i][j]表示从2出发到i点距离模m为j的最短路长度，求出最短路后，枚举j，如果dis[2][j] < k则拿m把dis[2][j]补到不小于k为止，更新答案，如果dis[2][j]>=k则直接更新答案
Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int maxn=60001;
const ll INF=2e18;
struct node
{
int v,mw;
ll w;
node(){};
node(int _v,int _mw,ll _w){v=_v,mw=_mw,w=_w;}
};
queue<node>que;
int T,d[4],mod;
ll k,dis[4][maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&k);
for(int i=0;i<4;i++)scanf("%d",&d[i]);
mod=2*min(d[0],d[1]);
for(int i=0;i<4;i++)
for(int j=0;j<mod;j++)
dis[i][j]=INF;
while(!que.empty())que.pop();
que.push(node(1,0,0));
while(!que.empty())
{
node now=que.front();
que.pop();
int v=now.v,mw=now.mw,tv,tmw;
ll w=now.w,tw;
if(dis[v][mw]<w)continue;
tv=(v+1)%4,tmw=(mw+d[v])%mod,tw=w+d[v];
if(dis[tv][tmw]>tw)dis[tv][tmw]=tw,que.push(node(tv,tmw,tw));
tv=(v+3)%4,tmw=(mw+d[tv])%mod,tw=w+d[tv];
if(dis[tv][tmw]>tw)dis[tv][tmw]=tw,que.push(node(tv,tmw,tw));
}
ll ans=INF;
for(int i=0;i<mod;i++)
if(dis[1][i]<k)
{
ll temp=(k-dis[1][i]+mod-1)/mod*mod+dis[1][i];
ans=min(ans,temp);
}
else ans=min(ans,dis[1][i]);
printf("%I64dn",ans);
}
return 0;
}

最后

以上就是自然冬天为你收集整理的HDU 6071 Lazy Running（模同余最短路）的全部内容，希望文章能够帮你解决HDU 6071 Lazy Running（模同余最短路）所遇到的程序开发问题。

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