python/TangDou/AcWing/P1339_Dijkstra.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 2510;          //结点数
const int M = 6200 * 2 + 10; //边数

int n, m; // n个结点，m条边
int s, t; //起点，终点

typedef pair<int, int> PII;
//邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int d[N];   //最短距离数组
bool st[N]; //是不是进过队列

//迪杰斯特拉
void dijkstra(int start) {
    memset(d, 0x3f, sizeof d);                        //初始化距离为无穷大
    memset(st, 0, sizeof st);                         //初始化为未出队列过
    d[start] = 0;                                     //出发点距离0
    priority_queue<PII, vector<PII>, greater<PII>> q; //小顶堆
    q.push({0, start});                               //出发点入队列
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                q.push({d[j], j});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dijkstra(s);
    cout << d[t] << endl;
    return 0;
}