给一个 n(1≤n≤10^6 ) 个点 m(1≤m≤10^6 ) 条边的无向图，求 s 到 t 的最短路的长度。 数据保证，s 出发可以到达 t,请从 stdin 读入。注意，输入可能很大 (>10MB) 第一行为四个正整数 n,m,s,t。 第二行起 m 行，每行三个非负整数 ui​,vi​,wi​(0≤wi​≤1)，表示从 ui​ 到 vi​ 有一条权值为 wi​ 的无向边。Time Limit: 1s Memory Limit: 128MB用C++实现，再不用STL的前提下

好的，这是一个经典的最短路径问题，可以使用 Dijkstra 算法来解决。以下是代码实现，不使用 STL 的优先队列，而是手写堆优化的 Dijkstra 算法。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m, s, t;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

int heap[N], cnt;

void insert(int x) {
    heap[cnt ++] = x;
    int i = cnt - 1, fa = i >> 1;
    while (i && dist[heap[i]] < dist[heap[fa]]) {
        swap(heap[i], heap[fa]);
        i = fa, fa = i >> 1;
    }
}

void remove() {
    heap[0] = heap[-- cnt];
    int i = 0, son = i * 2 + 1;
    while (son < cnt) {
        if (son + 1 < cnt && dist[heap[son + 1]] < dist[heap[son]]) son ++;
        if (dist[heap[son]] < dist[heap[i]]) {
            swap(heap[son], heap[i]);
            i = son, son = i * 2 + 1;
        } else break;
    }
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    insert(s);
    while (cnt) {
        int t = heap[0];
        remove();
        if (st[t]) continue;
        st[t] = true;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i], d = dist[t] + w[i];
            if (dist[j] > d) {
                dist[j] = d;
                insert(j);
            }
        }
    }
    return dist[t];
}

int main() {
    cin >> n >> m >> s >> t;
    memset(h, -1, sizeof h);
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    cout << dijkstra() << endl;
    return 0;
}

时间复杂度为 $O(m\log m)$，空间复杂度为 $O(n+m)$。