$O(n^2)$ 写法及用结构体的写法见：https://oj.33dai.cn/p/T1376/solution

$O(m\log{m})$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
const int INF = 2147483647; // 此时 INF+INF < INF
int n, m, s;
int dis[MAXN + 5];  // 当前最短路
bool vis[MAXN + 5]; // 是否确定了最短路
// e[u] 存所有以 u 为起点的边：<终点, 权值>
vector<pair<int, int>> e[MAXN + 5];
// <-dis[u], u>
priority_queue<pair<int, int>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
    }

    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[s] = 0;
    pq.push(make_pair(-0, s));
    while (!pq.empty())
    {
        // 找到当前最近的且未确定的点 u
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        // u 点的最短路可以确定了
        vis[u] = true;
        // 更新 u 的相邻点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pq.push(make_pair(-dis[v], v));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";

    return 0;
}

$O(m\log{n})$

手动实现二叉堆

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
const int INF = 2147483647; // 此时 INF+INF < INF
int n, m, s;
int dis[MAXN + 5];  // 当前最短路
bool vis[MAXN + 5]; // 是否确定了最短路
// e[u] 存所有以 u 为起点的边：<终点, 权值>
vector<pair<int, int>> e[MAXN + 5];
namespace Q
{
    // 点 i 在优先队列里面为 pq[idx[i]]
    // pq[idx[i]] 存的是 <dis[i],i>
    int idx[MAXN + 5];
    // <dis[u], u> 最小堆
    int tot; // pq[1]~pq[tot]
    pair<int, int> pq[MAXN + 5];
    // 把 pq[pos] 调整到合适位置
    void fresh(int pos)
    {
        // 看看要不要往上
        while (pos != 1 && pq[pos] < pq[pos / 2])
        {
            // pq[pos/2].second ~ pos/2
            // pq[pos].second ~ pos
            idx[pq[pos / 2].second] = pos;
            idx[pq[pos].second] = pos / 2;
            swap(pq[pos], pq[pos / 2]);
            pos = pos / 2;
        }
        // 看看要不要往下，没有儿子的时候不用管
        while (1)
        {
            int nxt = pos;
            if (pos * 2 <= tot &&
                pq[pos * 2] < pq[nxt])
                nxt = pos * 2;
            if (pos * 2 + 1 <= tot &&
                pq[pos * 2 + 1] < pq[nxt])
                nxt = pos * 2 + 1;
            if (pos != nxt)
            {
                // pq[nxt].second ~ nxt
                // pq[pos].second ~ pos
                idx[pq[nxt].second] = pos;
                idx[pq[pos].second] = nxt;
                swap(pq[pos], pq[nxt]);
                pos = nxt;
            }
            else
                break;
        }
    }
    void push(pair<int, int> x)
    {
        tot++;       // 加一个节点
        pq[tot] = x; // 把x放进去
        idx[x.second] = tot;
        fresh(tot); // 调整到合适位置
    }
    pair<int, int> top()
    {
        return pq[1];
    }
    bool empty()
    {
        return tot == 0;
    }
    void pop()
    {
        idx[pq[1].second] = 0;
        swap(pq[1], pq[tot]);
        tot--;
        if (tot != 0)
            fresh(1);
    }
    void update(int pos, pair<int, int> x)
    {
        pq[pos] = x;
        fresh(pos);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
    }

    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[s] = 0;
    Q::push(make_pair(0, s));
    while (!Q::empty())
    {
        // 找到当前最近的且未确定的点 u
        int u = Q::top().second;
        Q::pop();
        if (vis[u])
            continue;
        // u 点的最短路可以确定了
        vis[u] = true;
        // 更新 u 的相邻点
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                if (Q::idx[v] == 0)
                    Q::push(make_pair(dis[v], v));
                else
                    Q::update(Q::idx[v], make_pair(dis[v], v));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";

    return 0;
}