spfa
#include<iostream>
#include<queue>
using namespace std;
const int N(10000);
struct node
{
int adj,wei;
node *next;
};
node *g[N];
int n,en,source,dist[N];
bool inq[N];
queue<int> q;
void init()
{
int i,x,y,z;
node *p;
cin>>n>>en>>source;
memset(g,0,sizeof(g));
for (i=0;i<en;i++)
{
cin>>x>>y>>z;
p=new(node) ; p->adj=y; p->wei=z; p->next=g[x]; g[x]=p;
p=new(node); p->adj=x; p->wei=z; p->next=g[y]; g[y]=p;
}
}
void spfa()
{
memset(dist,0x7f,sizeof(dist));
dist[source]=0;
q.push(source);
memset(inq,0,sizeof(inq));
inq[source]=true;
while (!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
node *p=g[u];
while (p)
{
if (dist[u]+p->wei<dist[p->adj])
{
dist[p->adj]=dist[u]+p->wei;
if (!inq[p->adj])
{
q.push(p->adj);
inq[p->adj]=true;
}
}
p=p->next;
}
}
}
int main()
{
init();
spfa(); // shortest path faster algorithm
for (int i=1;i<=n;i++) cout<<dist[i]<<" "; cout<<endl;
system("pause");
return 0;
}
posted on 2011-11-02 22:09
龙在江湖 阅读(696)
评论(0) 编辑 收藏 引用 所属分类:
图论