用c++数据结构O(n+m) 的做法来解决这个问题，不能使用stl容器，时间限制： 1000 ms以内，不能超时，内存空间限制： 244 MiB以内给出C++代码：给一个n (1≤n≤106) 个点m(1≤m≤106) 条边的无向图，求 s 到 t 的最短路的长度。 输入要求：请从 stdin 读入。注意，输入可能很大 (>10MB)第一行为四个正整数n,m,s,t。第二行起 m 行，每行三个非负整数 ui,vi,wi(0≤wi≤1)，表示从 ui 到 vi 有一条权值为 wi 的无向边。

可以使用 SPFA 算法来求解最短路的长度，时间复杂度为 O(km)，其中 k 为一个常数，一般情况下不会超过 2。

具体实现如下：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
const int M = 2e6 + 10;
const int INF = 0x3f3f3f3f;

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

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

bool spfa(int start)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[start] = 0;

    int q[N], hh = 0, tt = 0;
    q[tt ++] = start;
    st[start] = true;

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

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return dist[t] < INF;
}

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(s))
        cout << dist[t] << endl;
    else
        cout << -1 << endl;

    return 0;
}