HDU6071-最短路

72 阅读 0 评论 48 点赞

我是靠谱客的博主落寞唇彩，最近开发中收集的这篇文章主要介绍HDU6071-最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=6071

四个点围成一个环，相邻两点之间存在路径，问从2号点出发最后再次回到二号点，在路程大于等于K的情况下的最小路程量。

我们令m=min(d1,d2)*2,可以想做是回到2号点之后再重复的走若干个m后的路程。（当然m也可以是max(d1,d2)*2,因为只要和2相邻即可)。

f[i][j]表示从2出发达到i之后，走过路程f[i][j]%m=j的最小路程，跑一遍dij，最后统计结果如果不足k就加上m补足。

这样之所以是正确的在于考虑了所有的情况，对于同一个模m剩余系里面的路程他们之间的差值一定是m的倍数，所以选出一个最小的如果不足k用m补足

相当于还原到另一个路程上了，也能找到最优解。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<bits/stdc++.h>
 8 #define LL long long
 9 using namespace std;
10 #define LL long long
11 struct Edge
12 {
13 
LL u,w;
14 };
15 struct node
16 {
17 
LL u,w;
18
bool operator<(const node&chs)const{
19
return w>chs.w;
20 
}
21 };
22 LL f[4][60010];
23 vector<Edge> g[4];
24 void dij(LL m)
25 {
26
memset(f,-1,sizeof(f));
27
f[1][0]=0;
28
priority_queue<node>q;
29
q.push(node{1,0});
30
while(!q.empty()){
31
int u=q.top().u,
32
w=q.top().w;
33 
q.pop();
34
for(int i=0;i<g[u].size();++i){
35
if(w+g[u][i].w<f[g[u][i].u][(w+g[u][i].w)%m]||f[g[u][i].u][(w+g[u][i].w)%m]==-1){
36
f[g[u][i].u][(w+g[u][i].w)%m]=w+g[u][i].w;
37
q.push(node{g[u][i].u,f[g[u][i].u][(w+g[u][i].w)%m]});
38 
}
39 
}
40 
}
41 }
42 int main()
43 {
44
LL n,m,i,j,k,d[4],t;
45
cin>>t;
46
while(t--){
47
cin>>k;
48
for(i=0;i<4;++i)cin>>d[i],g[i].clear();
49
g[0].push_back(Edge{1,d[0]});
50
g[0].push_back(Edge{3,d[3]});
51
52
g[1].push_back(Edge{0,d[0]});
53
g[1].push_back(Edge{2,d[1]});
54
55
g[2].push_back(Edge{1,d[1]});
56
g[2].push_back(Edge{3,d[2]});
57
58
g[3].push_back(Edge{0,d[3]});
59
g[3].push_back(Edge{2,d[2]});
60
61
m=min(d[0],d[1])*2;
62 
dij(m);
63
LL ans=1e18;
64
for(i=0;i<m;++i){
65
if(f[1][i]==-1) continue;
66
if(f[1][i]>=k) ans=min(ans,f[1][i]);
67
else{
68
69
ans=min(ans,f[1][i]+
70
(k-f[1][i])/m*m+((k-f[1][i])%m>0)*m);
71 
}
72 
}
73
cout<<ans<<endl;
74 
}
75
return 0;
76 }