//dijkstra邻接矩阵实现
//#include<fstream>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<iterator>
using namespace std;
const int N(1000);
int dist[N];
int prev[N];
int g[N][N];
int n,en,source;
bool f[N];
//ifstream cin("data.in");
//ofstream cout("data.out");
void init()
{
int x,y,z;
cin>>n>>en>>source;
memset(g,0x7f,sizeof(g));
for (int i=0;i<en;i++)
{
cin>>x>>y>>z;
g[x][y]=g[y][x]=z;
}
for (int i=1;i<=n;i++) g[i][i]=0;
for (int i=1;i<=n;i++) dist[i]=g[source][i];
for (int i=1;i<=n;i++) prev[i]=source;
}
void dijkstra()
{
int i,j,u;
memset(f,0,sizeof(f));
f[source]=true;
u=source;
for (i=1;i<n;i++)
{
int tmp=0x7f7f7f7f;
for (j=1;j<=n;j++)
if (!f[j]&&dist[j]<tmp)
{
u=j;
tmp=dist[j];
}
f[u]=true;
for (j=1;j<=n;j++)
if (!f[j]&&g[u][j]<0x7f7f7f7f)
if (dist[u]+g[u][j]<dist[j])
{
dist[j]=dist[u]+g[u][j];
prev[j]=u;
}
}
}
int main()
{
init();
dijkstra();
copy(dist+1,dist+n+1,ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
posted on 2011-10-31 12:51
龙在江湖 阅读(148)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
算法