我是靠谱客的博主 耍酷黑裤，这篇文章主要介绍HDU1690(最短路 两种解法 Dijkstra和Floyd)HDU1690(最短路 两种解法 Dijkstra和Floyd)，现在分享给大家，希望可以做个参考。
HDU1690(最短路 两种解法 Dijkstra和Floyd)
- 题目链接
Dijkstra
- 解题思路（菜鸡一只，可能有错误，如果各位看出来哪里有问题的话欢迎指出，谢谢了）：刚开始我就是用Dijkstra做的，每次交上去都是Runtime Error(ACCESS_VIOLATION)，后来看到网上的题解发现在Dijlstra中加一个
复制代码
1
2
if(pos==end)
break;然后代码就过了，具体原因我还是没有想清楚，我觉得可能每次都把起点到所有点的最短距离算出来可能就超时了，（如果各位知道为什么的话可不可以告诉我一下）:please:这道题要用%I64d，而且inf要很大才行
- 代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dir[110];
long long map[110][110];
long long cast[110];
int vis[110];
int n;
const long long inf=1e18;
void
picture(long long beg,long long end)
{
memset(vis,0,sizeof(vis));
long long i,j,pos,minn;
for(i=1;i<=n;i++)
cast[i]=map[beg][i];
vis[beg]=1;
for(i=1;i<=n;i++)
{
minn=inf;
for(j=1;j<=n;j++)
{
if(cast[j]<minn&&!vis[j])
{
minn=cast[j];
pos=j;
}
}
if(pos==end)
break;
vis[pos]=1;
for(j=1;j<=n;j++)
{
if(cast[pos]+map[pos][j]<cast[j]&&!vis[j])
cast[j]=cast[pos]+map[pos][j];
}
}
}
int main()
{
int nn,cnt=0;
scanf("%d",&nn);
while(nn--)
{
long long l1,l2,l3,l4,c1,c2,c3,c4,m,i,j;
scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d",&l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4);
scanf("%I64d %I64d",&n,&m);
for(i=1;i<=n;i++)
scanf("%I64d",&dir[i]);
for(i=1;i<=n;i++)//这里写的比较啰嗦，可以直接写在一个函数里
{
for(j=1;j<=n;j++)
{
long long
x=abs(dir[i]-dir[j]);
if(x==0)
{
map[i][j]=0;
}
else if(x<=l1)
{
map[i][j]=c1;
map[j][i]=c1;
}
else if(x<=l2)
{
map[i][j]=c2;
map[j][i]=c2;
}
else if(x<=l3)
{
map[i][j]=c3;
map[j][i]=c3;
}
else if(x<=l4)
{
map[i][j]=c4;
map[j][i]=c4;
}
else
{
map[i][j]=inf;
map[j][i]=inf;
}
}
}
printf("Case %d:n",++cnt);
while(m--)
{
long long beg,end;
scanf("%I64d %I64d",&beg,&end);
picture(beg,end);
if(cast[end]==inf)
printf("Station %I64d and station %I64d are not attainable.n",beg,end);
else
{
printf("The minimum cost between station %I64d and station %I64d is %I64d.n",beg,end,cast[end]);
}
}
}
return 0;
}Floyd
- 这个直接上代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dir[110];
long long map[110][110];
int n;
const long long inf=1e18;
void
Floyd()
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
}
}
}
int main()
{
int nn,cnt=0;
scanf("%d",&nn);
while(nn--)
{
long long l1,l2,l3,l4,c1,c2,c3,c4,m,i,j;
scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d",&l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4);
scanf("%I64d %I64d",&n,&m);
for(i=1;i<=n;i++)
scanf("%I64d",&dir[i]);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
long long
x=abs(dir[i]-dir[j]);
if(x==0)
{
map[i][j]=0;
}
else if(x<=l1)
{
map[i][j]=c1;
map[j][i]=c1;
}
else if(x<=l2)
{
map[i][j]=c2;
map[j][i]=c2;
}
else if(x<=l3)
{
map[i][j]=c3;
map[j][i]=c3;
}
else if(x<=l4)
{
map[i][j]=c4;
map[j][i]=c4;
}
else
{
map[i][j]=inf;
map[j][i]=inf;
}
}
}
printf("Case %d:n",++cnt);
Floyd();
while(m--)
{
long long beg,end;
scanf("%I64d %I64d",&beg,&end);
if(map[beg][end]==inf)
printf("Station %I64d and station %I64d are not attainable.n",beg,end);
else
{
printf("The minimum cost between station %I64d and station %I64d is %I64d.n",beg,end,map[beg][end]);
}
}
}
return 0;
}
最后
以上就是耍酷黑裤最近收集整理的关于HDU1690(最短路 两种解法 Dijkstra和Floyd)HDU1690(最短路 两种解法 Dijkstra和Floyd)的全部内容，更多相关HDU1690(最短路内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复