求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5, MAXM=1e5+5;
int n, m, s;
struct Edge
{
    int u, v, w, nxt;
}edge[MAXM];
int cnt, head[MAXN];
struct node
{
    int a, b;
    bool operator <(const node &x) const
    {
        return x.a<a;
    }
};

priority_queue<node> q;

void add(int u, int v, int w)
{
    edge[++cnt]={u, v, w, head[u]};
    head[u]=cnt;
}

int dis[MAXN];
bool check[MAXN];

int main()
{
    memset(dis, 0x3f, sizeof(dis));
    cin>>n>>m>>s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin>>u>>v>>w;
        add(u, v, w);
    }
    dis[s]=0;
    q.push({0, s});
    while(q.size())
    {
        node k=q.top();
        q.pop();
        int b=k.b;
        if(check[b]) continue;
        check[b]=1;
        for(int i=head[b]; i; i=edge[i].nxt)
        {
            int v=edge[i].v, w=edge[i].w;
            if(dis[v]>dis[b]+w)
            {
                dis[v]=dis[b]+w;
                if(!check[v])
                    q.push({dis[v], v});
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        cout<<dis[i]<<" ";
    }

}