给一个 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的前提下用SPFA算法实现

好的，以下是不使用 STL 的代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010, M = 2000010;

int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx;  // 邻接表存图
int dist[N];  // 存储起点到各个点的最短距离
bool st[N];  // 存储每个点的最短路是否已经确定
int q[N];  // SPFA 算法中的队列
int hh, tt;  // 队列的头和尾指针

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

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);  // 初始化 dist 数组，全部赋为 INF
    dist[s] = 0;

    q[0] = s;
    hh = 0, tt = 1;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])  // 遍历 t 的所有出边
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])  // 如果从 t 点到 j 点的距离更短
            {
                dist[j] = dist[t] + w[i];  // 更新 dist[j]
                if (!st[j])  // 如果队列中已经存在 j，不用将 j 重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;

                    if (tt == hh)  // 队列已满，扩容
                    {
                        cout << "队列已满，扩容" << endl;
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

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);
    }

    if (spfa()) cout << dist[t] << endl;
    else puts("无解");

    return 0;
}

这里的实现方式是 SPFA 算法，用一个队列来维护待更新的点。首先将起点 s 加入队列中，然后每次取出队首的点 t，遍历所有从 t 出发的边，如果从 t 到达它们的另一个端点 j 的距离 dist[j] 可以通过从 t 转移得到更小的值，那么就更新 dist[j] 并将 j 加入队列中。由于每个点可能被更新多次，因此需要使用一个 bool 数组 st 来记录每个点是否在队列中，避免重复插入。如果某个点被更新的次数超过了 n 次，就说明存在负环，算法应该返回无解。

为了避免队列溢出，需要使用循环队列来实现，同时需要定时扩容。在这里的实现中，队列的最大长度为 N，当队列已满时需要扩容。