HDU 6071 最短路

题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=6071

题目大意 ：以2为起点，并且以2为终点才算一圈，可以跑任意多个这样的圈，求大于等于K的最短距离

解题思路 ：设W=2*min(2到3，2到1)，这样的话W就代表以2为起点并且以2为终点的圈里面距离最小的那一圈，W可以是以2为起点并且以2为终点的圈里面任意一个，这里选最小的是为了降低时间复杂度，这样的话答案ans的范围就是[k,k+w-1],左边界我们已经很清楚了，等于K的时候是最小的，最差的情况就是跑完之后是k-1，我们只需要再跑一个最小圈就可以了，所以这里用的同余，d[i][j],i代表以i+1为终点，j代表距离%w=j，d[i][j]就是终点是i+1，且距离%w=j里面的最短路

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define LL long long
#define read(a) scanf("%d",&a)
typedef pair<LL,int> P;
LL d[4][100000+10],k,x1,x2,x3,x4,w;
struct node
{
int v;
LL dis;
node(){}
node(int a,LL b): v(a),dis(b){}
};
vector<node> e[5];
void spfa(int u)
{
priority_queue<P,vector<P>,greater<P>>q;
for(int i=0;i<4;i++)
{
for(int j=0;j<w;j++)
d[i][j]=20000000000000;
}
q.push(P(0,u));
while(!q.empty())
{
int x=q.top().second;
LL mod=q.top().first;
q.pop();
if(mod>d[x][mod%w])
continue;
for(auto &y:e[x])
{
int to=y.v;
LL di=mod+y.dis;
if(d[to][di%w]>di)
{
d[to][di%w]=di;
q.push(P(di,to));
}
}
}
}
void work()
{
for(int i=0;i<5;i++)
e[i].clear();
scanf("%lld%lld%lld%lld%lld",&k,&x1,&x2,&x3,&x4);
e[0].push_back(node(1,x1));
e[0].push_back(node(3,x4));
e[1].push_back(node(0,x1));
e[1].push_back(node(2,x2));
e[2].push_back(node(1,x2));
e[2].push_back(node(3,x3));
e[3].push_back(node(0,x4));
e[3].push_back(node(2,x3));
w=min(x1,x2)*2;
LL ans=k+2*w;
spfa(1);
for(int i=0;i<w;i++)
{
LL shor=k-d[1][i];
if(shor<=0)
ans=min(ans,d[1][i]);
else ans=min(ans,d[1][i]+shor/w*w+(shor%w>0)*w);
}
printf("%lldn",ans);
}
int main()
{
int T;
read(T);
while(T--)
{
work();
}
return 0;
}

最后

以上就是诚心大地为你收集整理的HDU 6071 最短路的全部内容，希望文章能够帮你解决HDU 6071 最短路所遇到的程序开发问题。

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