#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N(100005);
struct node{
int adj,w;
node *next;
};
node *g[N]={0};
int n,dist[N];
bool inq[N]={0};
queue<int> q;
void spfa(int x)
{
fill(dist,dist+n+1,0x7fffffff);
dist[x]=0;
q.push(x);
inq[x]=true;
while (!q.empty())
{
int k=q.front();
q.pop();
inq[k]=false;
node *p=g[k];
while (p)
{
if (dist[k]+p->w<dist[p->adj])
{
dist[p->adj]=dist[k]+p->w;
if (!inq[p->adj])
{
q.push(p->adj);
inq[p->adj]=true;
}
}
p=p->next;
}
}
}
int main()
{
int en;
node *p;
cin>>n>>en;
for (int i=0,x,y,z;i<en;i++)
{
cin>>x>>y>>z;
p=new(node); p->adj=y; p->w=z; p->next=g[x]; g[x]=p;
//p=new(node); p->adj=x; p->w=z; p->next=g[y]; g[y]=p;
}
spfa(1);
for (int i=1;i<=n;i++) cout<<dist[i]<<" ";
cout<<endl;
system("pause");
return 0;
}
参考数据:
5 7
1 2 10
1 5 100
1 4 30
2 3 50
4 3 20
3 5 10
4 5 60
参考输出：
0 10 50 30 60
posted on 2013-11-03 11:43
龙在江湖 阅读(1707)
评论(0) 编辑 收藏 引用 所属分类:
图论