簡短的最短路問題
Dijkstra算法求解
[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
const int N=202;
const int INF=1<<28;
int path[N][N],d[N];
bool s[N];
void Dijkstra(int first,int last,int n)
{
memset(s,false,sizeof(s));
int i,j,u;
for(i=0;i<n;i++)
d[i]=path[first][i];
d[first]=0;s[first]=true;
for(i=0;i<n;i++)
{
int minn=INF;
for(j=0;j<n;j++)
if(!s[j]&&d[j]<minn)
minn=d[u=j];
s[u]=true;
for(j=0;j<n;j++)
if(!s[j]&&d[j]>d[u]+path[u][j])
d[j]=d[u]+path[u][j];
}
}
int main()
{
int i,j,n,m,a,b,x,start,end;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
path[i][j]=INF;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&x);
if(x<path[a][b])
path[a][b]=path[b][a]=x;
}
scanf("%d%d",&start,&end);
Dijkstra(start,end,n);
if(d[end]==INF) printf("-1\n");
else printf("%d\n",d[end]);
}
return 0;
}
floyd算法求解
[cpp]
#include<iostream>
#include<cstdio>
const int N=202;
const int INF=1<<28;
int path[N][N];
int floyd(int s,int t,int n)
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
{
if(path[i][k]!=INF)//優化，減少不必要的時間損耗
for(j=0;j<n;j++)
if(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
return path[s][t];
}
int main()
{
int i,j,n,m,a,b,x,s,t,ans;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j) path[i][j]=0;
else path[i][j]=INF;
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&x);
if(x<path[a][b])
path[a][b]=path[b][a]=x;
}
scanf("%d%d",&s,&t);
ans=floyd(s,t,n);
printf("%d\n",ans<INF?ans:-1);
}
return 0;
}
