大红大紫 /kk

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 2147483647
#define MAXN 500050 + 105
#define pr pair<int,int>

int n, m,s;
int tot, head[MAXN], ver[MAXN], val[MAXN], nxt[MAXN];
int dist[MAXN];
bool visit[MAXN];

void insert(int u, int v, int w)
{
    ++tot;
    ver[tot]=v;
    val[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}

void init()
{
    for(int i=1;i<=n;i++)
        dist[i]=INF,visit[i]=false;
}

void dij(int s)
{
    priority_queue<pr >q;
    
    dist[s]=0;
    q.push(make_pair(0,s));

    while(!q.empty())
    {
        int fro=q.top().second;
        q.pop();
        
        if(visit[fro]) continue;
        visit[fro]=true;
        
        for(int i=head[fro];i;i=nxt[i])
        {
            int y=ver[i],w=val[i];
            if(dist[y]>dist[fro]+w)
            {
                dist[y]=dist[fro]+w;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);
    }

    init(),dij(1);

    for(int i=1;i<=n;i++)
        printf("%d ",dist[i]);

    return 0;
}