朴素版dijkstra算法时间复杂度是 $O(n^2)$

堆优化版本dijkstra算法时间复杂度是 $O(mlog(n))$

bellman算法时间复杂度是 $O(n*m)$

spfa算法时间复杂度是 $O(m)$

题目中给数据为稀疏图，根据计算我们使用spfa算法

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
const int N = 2510, M = 6200 * 2 + 10;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
//使用标记数组，确保每个元素只入队一次
int n, m, start, ed;
queue<int> q;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int sp() {
    memset(d, 0x3f, sizeof d);
    d[start] = 0;
    q.push(start);
    st[start] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j] = d[t] + w[i];
                if (!st[t]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return d[ed];
}

int main() {
    cin >> n >> m >> start >> ed;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c); //题目中给的是无向图
    }
    cout << sp() << endl;
}