找不到问题呀!
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int head[100005],cnt=0;
int dis[100005],vis[100005]={0};
struct edge
{
int v,w,next;
}e[500005];
struct node
{
int u,d;
bool operator <(const node& rhs) const
{
return d>rhs.d;
}
};
void addedge(int u,int v,int w)
{
e[cnt++].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void dij()
{
for(int i = 1;i<=n;i++) dis[i]=0x3f;
priority_queue<node> Q;
Q.push((node){s,0});
dis[s]=0;
while(!Q.empty())
{
node fr=Q.top(); Q.pop();
int u=fr.u; int d=fr.d;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int y = e[i].v;
if(dis[y]>dis[u]+e[i].w )
{
dis[y]=dis[u]+e[i].w;
if(!vis[y])
{
Q.push((node){dis[y], y} );
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i = 1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
addedge(a,b,c);
}
dij();
for(int i = 1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}