HDU1690(最短路两种解法 Dijkstra和Floyd)HDU1690(最短路两种解法 Dijkstra和Floyd)

60 阅读 0 评论 40 点赞

我是靠谱客的博主耍酷黑裤，最近开发中收集的这篇文章主要介绍HDU1690(最短路两种解法 Dijkstra和Floyd)HDU1690(最短路两种解法 Dijkstra和Floyd)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

HDU1690(最短路两种解法 Dijkstra和Floyd)

题目链接

Dijkstra

解题思路（菜鸡一只，可能有错误，如果各位看出来哪里有问题的话欢迎指出，谢谢了）：刚开始我就是用Dijkstra做的，每次交上去都是Runtime Error(ACCESS_VIOLATION)，后来看到网上的题解发现在Dijlstra中加一个

if(pos==end)
break;

然后代码就过了，具体原因我还是没有想清楚，我觉得可能每次都把起点到所有点的最短距离算出来可能就超时了，（如果各位知道为什么的话可不可以告诉我一下）:please:这道题要用%I64d，而且inf要很大才行

代码

#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

这个直接上代码

#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;
}