为什么过不了w(゚Д゚)w
求dalao解答
#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define inf 2147483647
using namespace std;
int n,m,s,dis[N];
int head[N],nxt[N*2],to[N],val[N*2],cnt;
bool vis[N];
struct node
{
int w,v;
inline bool operator <(const node &x)const
{
return w>x.w;
}
};
priority_queue<node>q;
inline int read()
{
int x=0,k=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
void dijkstra()
{
dis[s]=0;
q.push((node){0,s});
while(!q.empty())
{
int u=q.top().v;
q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=nxt[i])
{
if(dis[to[i]]>(ll)dis[u]+val[i])
{
dis[to[i]]=dis[u]+val[i];
q.push((node){dis[to[i]],to[i]});
}
}
}
return ;
}
void add(int x,int y,int z)
{
cnt++;
nxt[cnt]=head[x];
to[cnt]=y;
val[cnt]=z;
head[x]=cnt;
return ;
}
int main()
{
int n,m;
n=read();m=read();s=read();
for(int i=1;i<=m;i++)
{
int u,v,w;
u=read();v=read();w=read();
add(u,v,w);
}
for(int i=1;i<=n;i++)
{
dis[i]=inf;
}
dijkstra();
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}