手写堆，按照当前点的ans进行选择。

# include <bits/stdc++.h>
# include <iostream>

using namespace std;

struct Node
{
    long long dis;
    int to;
    struct Node* nxt;
};

struct Head
{
    struct Node* nxt;
};

struct Head p[100005];
long long ans[100005];
int vis[100005];

struct Node* ini()
{
    struct Node* tmp = (struct Node*) malloc (sizeof(struct Node));
    tmp->nxt = NULL;
    return tmp;
};

int heap[1000005*4];
int len;

void add(int x)
{
    heap[++len] = x;
    int now = len;

    while (now > 1)
    {
        int fa = now/2;
        if (ans[heap[now]] < ans[heap[fa]])
        {
            swap(heap[now],heap[fa]);
        }
        now = fa;
    }

    return ;
}

void del()
{
    heap[1] = heap[len--];
    int now = 1;

    while (now*2 <= len)
    {
        int son = now*2;
        if (son+1 <= len && ans[heap[son+1]] < ans[heap[son]])
        {
            son++;
        }
        if (ans[heap[son]] < ans[heap[now]])
        {
            swap(heap[son],heap[now]);
        }
        now = son;
    }

    return ;
}

int main (void)
{
    int n,m,s;
    scanf ("%d %d %d",&n,&m,&s);

    for (int i=1;i<=n;i++)
    {
        ans[i] = LONG_LONG_MAX;
        p[i].nxt = NULL;
    }

    for (int i=0;i<m;i++)
    {
        int s,t;
        long long dis;
        scanf ("%d %d %lld",&s,&t,&dis);
        struct Node* tmp = ini();
        tmp->nxt = p[s].nxt;
        tmp->to = t;
        tmp->dis = dis;
        p[s].nxt = tmp;
    }

    add(s);
    ans[s] = 0;

    while (len)
    {
        int x = heap[1];
        del();
        if (vis[x])
        {
            continue;
        }
        vis[x] = 1;

        for (struct Node* tmp=p[x].nxt;tmp!=NULL;tmp=tmp->nxt)
        {
            int y = tmp->to;
            if (!vis[y])
            {
                if (ans[x] + tmp->dis < ans[y])
                {
                    ans[y] = ans[x] + tmp->dis;
                    add(y);
                }
            }
        }

    }

    for (int i=1;i<=n;i++)
    {
        printf ("%lld ",ans[i]);
    }

    return 0;
}