#include<iostream>
using namespace std;
int n,g[1000][1000],dist[1000];
bool f[1000]={0};
int minv()
{
int k=0x7fffffff,j;
for (
int i=0;i<n;i++)
if (!f[i]&&dist[i]<k)
{
j=i;
k=dist[i];
}
return j;
}
void shortpath()
{
f[0]=
true;
int j;
for (
int i=1;i<n;i++)
{
j=minv();
f[j]=
true;
for (
int k=0;k<n;k++)
if (g[j][k]!=0x7fffffff)
if (!f[k]&&dist[j]+g[j][k]<dist[k])
dist[k]=dist[j]+g[j][k];
}
}
int main()
{
int en,x,y;
cin>>n>>en;
for (
int i=0;i<n;i++)
for (
int j=0;j<n;j++)
g[i][j]=0x7fffffff;
for (
int i=0;i<n;i++) g[i][i]=0;
for (
int i=0;i<en;i++)
cin>>x>>y>>g[x][y];
for (
int i=0;i<n;i++) dist[i]=g[0][i];
shortpath();
for (
int i=0;i<n;i++) cout<<dist[i]<<" ";
cout<<endl;
system("pause");
return 0;
}
输入：
6 11
0 1 5
0 2 30
0 3 18
1 2 12
1 3 10
2 4 25
3 0 15
3 4 8
4 1 5
4 2 20
4 5 4
输出：
0 5 17 15 23 27
posted on 2012-12-25 17:00
龙在江湖 阅读(173)
评论(0) 编辑 收藏 引用 所属分类:
图论