|
r<pii>vec[MAX];
int dis[MAX];
void dij(int s)
{
memset(dis,INF,sizeof(dis));
dis[s]=0;
int qu[MAX],he=0,ta=0,i;
qu[ta++]=s;
while(he<ta)
{
int u=qu[he++];
for(i=0;i<vec[u].size();i++)
{
int v=vec[u][i].first;
int w=vec[u][i].second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
qu[ta++]=v;
}
}
}
}
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
vec[u].push_back(pii(v,w));
}
int s;
cin>>s;
dij(s);
for(i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
return 0;
}
dijkstra邻接表版本
|