#3 wa
代码如下:
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 10005
#define maxm 500005
#define INF 1234567890
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;
}
#define pii pair<int,int>
struct edge{
int u,v,w;
int nxt;
};
edge g[maxm];
int head[maxn],e,n,m,s,vis[maxn],dis[maxn];
void add(int u,int v,int w)
{
g[++e].u=u;
g[e].v=v;
g[e].w=w;
g[e].nxt=head[u];
head[u]=e;
}
priority_queue < pair < int,int > > pq;
void dijkstra(/*int S*/)
{
for(int i=1;i<=n;i++) dis[i]=2e9,vis[i]=false;
dis[s]=0;
pq.push(make_pair(0,s));
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=g[i].nxt)
{
int v=g[i].v;
if(dis[u]+g[i].w<dis[v])
{
dis[v]=dis[u]+g[i].w;
pq.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
n=read(),m=read(),s=read();
for(int i=1,x,y,z;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y,z);
}
dijkstra();
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}