HDU6071 Lazy Running

题目链接

题意

​ 存在一个含有4个点的图，给定1-2，2-3，3-4，4-1四条无向边的长度 d1,2,d2,3,d3,4,d4.1 和一个 K 值。问起点和终点均为2，可以不断在各个点之间不断往返，使得所经过的路程总长 S≥K 时的最小 S 为多少。

分析

​ 来自题解的思路。设 w=2min(d2,1,d2,3) ，显然我们可以通过不断往返这一段路程使得总后的总路程满足要求。设往返前经过的路程为 d ，则这个推论可以表示为d+a1×w≥K 。在 d≤K 时，等价于 dmodw+a2×w≥K ；而 d>K 的情况，实际可以直接判断是否为最小值。问题此时就转换成找到到达每个点特定取模值下的最短路问题，一次优先队列即可。详细可以参考代码理解。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 60600
#define eps 1e-7
#define lson rt<<1
#define rson rt<<1|1
#define LL long long
struct Node{
LL d;
int curidx,md;
Node(){}
Node(int _curidx,int _md,LL _d):curidx(_curidx),md(_md),d(_d){}
friend bool operator<(Node n1,Node n2){
return n1.d>n2.d;
}
};
int dis[5][5];
bool vis[5][60600];
int main(){
int T;
cin>>T;
memset(dis,-1,sizeof(dis));
while(T--){
LL K;
memset(vis,0,sizeof(vis));
scanf("%I64d %d %d %d %d",&K,&dis[1][2],&dis[2][3],&dis[3][4],&dis[4][1]);
dis[2][1]=dis[1][2];dis[3][2]=dis[2][3];dis[1][4]=dis[4][1];
dis[4][3]=dis[3][4];
int w=2*min(dis[1][2],dis[2][3]);
priority_queue<Node> q;
q.push(Node(2,0,0));
LL ans=(K+w-1)/w*w;
while(!q.empty()){
Node tmp=q.top();
q.pop();
if(vis[tmp.curidx][tmp.md])
continue;
vis[tmp.curidx][tmp.md]=1;
if(tmp.curidx==2){
if(tmp.d>=K)
ans=min(tmp.d,ans);
else{
LL tot=K/w*w+tmp.md;
if(tot<K)
tot+=w;
ans=min(ans,tot);
}
}
for(int i=1;i<=4;++i){
if(dis[tmp.curidx][i]!=-1){
int mm=(tmp.md+dis[tmp.curidx][i])%w;
q.push(Node(i,mm,tmp.d+dis[tmp.curidx][i]));
}
}
}
printf("%I64dn",ans);
}
}

最后

以上就是能干飞鸟为你收集整理的HDU6071 Lazy Running的全部内容，希望文章能够帮你解决HDU6071 Lazy Running所遇到的程序开发问题。

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