算法：堆优化 Dij

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<vector>
#include<set>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

#define inf 0x3f3f3f3f
#define int long long
#define endl '\n'

const int maxn = 10010;
const int maxm = 500010;

struct node {
    int v, w;
    node() {

    }
    node(int vv, int ww) {
        v = vv;
        w = ww;
    }
};

vector<node> g[maxn];
int n, m, s;
int dis[maxn];
set<pair<int, int>> minHeap;

signed main() {
    IOS;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(node(v, w));
        g[v].push_back(node(u, w));
    }
    for (int i = 0;i < maxn;i++) {
        dis[i] = inf;
    }
    dis[s] = 0;

    minHeap.insert(make_pair(0, s));
    while (minHeap.size()) {
        int mind = minHeap.begin()->first;
        int v = minHeap.begin()->second;
        minHeap.erase(minHeap.begin());
        for (int i = 0;i < g[v].size();i++) {
            if (dis[g[v][i].v] > dis[v] + g[v][i].w) {
                minHeap.erase(make_pair(dis[g[v][i].v], g[v][i].v));
                dis[g[v][i].v] = dis[v] + g[v][i].w;
                minHeap.insert(make_pair(dis[g[v][i].v], g[v][i].v));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dis[i] > inf) {
            cout << inf << ' ';
        }
        else cout << dis[i] << " ";
    }
    return 0;
}

//Fununugugu Code

我太菜了 /dk/dk/dk