求调

#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt;
const int INF=INT_MAX;
struct node
{
    int v,w;
    friend bool operator <(node a,node b)
    {
        return a.w>b.w;
    }
}tmp;
int val[500010];
int dis[500010];
priority_queue<node>q;
int h[50010];
int to[500010],nxt[500010];
bool vis[500010];
void add(int a,int b,int c)
{
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
inline int Dijkstra()
{
    for(int i=0;i<=n;i++)
    {
        dis[i]=INF;
    }
    dis[s]=0;
    tmp.v=s,tmp.w=0;
    q.push(tmp);
    while(!q.empty())
    {
        int u=q.top().v;
        q.pop();
        if(vis[u])
        {
            continue;
        }
        vis[u]=1;
        for(int i=h[u];i;i=nxt[i])
        {
            if(dis[to[i]]>(long long)dis[u]+val[i])
            {
                dis[to[i]]=dis[u]+val[i];
                tmp.w=dis[to[i]],tmp.v=to[i];q.push(tmp);
            }
        }
    }
}
int read()
{
    int p=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        p=p*10+(c-'0'),c=getchar();
    }
    return p;
}
void write(int l)
{
    if(l>=10)
    {
        write(l/10);
    }
    putchar(l%10+'0');
}
int main()
{
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        a=read();
        b=read();
        c=read();
        add(a,b,c); 
    }
    Dijkstra();
    for(int i=1;i<=n;i++)
    {
        write(dis[i]),putchar(' ');
    }
    return 0;
}

记录