#include <cstdio> #include <cstring> using namespace std; const int N = 1000010; int n, m, s, t; bool st[N]; int h[N], e[N], w[N], ne[N], idx; int d[N]; void add(int u, int v, int weight) { e[idx] = v, w[idx] = weight, ne[idx] = h[u], h[u] = idx ++; } int dijkstra() { memset(d, 0x3f, sizeof d); d[s] = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || d[t] > d[j])) t = j; st[t] = true; for (int j = h[t]; j != -1; j = ne[j]) { int k = e[j]; if (d[k] > d[t] + w[j]) d[k] = d[t] + w[j]; } } return d[t]; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); memset(h, -1, sizeof h); while (m -- ) { int u, v, weight; scanf("%d%d%d", &u, &v, &weight); add(u, v, weight); add(v, u, weight); } printf("%d\n", dijkstra()); return 0; }这段代码超时严重，帮我在不使用stl容器的前提下优化它

这段代码的时间复杂度为 O(n^2)，可以使用堆优化的 Dijkstra 算法将时间复杂度降低到 O(mlogn)。

以下是使用数组手写堆优化的代码：

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1000010;

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

void add(int u, int v, int weight)
{
    e[idx] = v, w[idx] = weight, ne[idx] = h[u], h[u] = idx ++;
}

void heap_swap(int i, int j, int q[])
{
    int t = q[i];
    q[i] = q[j], q[j] = t;
}

void down(int u, int q[])
{
    int t = u;
    if (u * 2 <= q[0] && d[q[u * 2]] < d[q[t]]) t = u * 2;
    if (u * 2 + 1 <= q[0] && d[q[u * 2 + 1]] < d[q[t]]) t = u * 2 + 1;
    if (u != t) heap_swap(u, t, q), down(t, q);
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[s] = 0;

    int q[N] = {0}, hh = 0, tt = 0;
    q[0] = 1, q[1] = s;

    while (q[0])
    {
        int t = q[1];
        heap_swap(1, q[0] --, q);
        down(1, q);

        if (st[t]) continue;
        st[t] = true;

        for (int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];
            if (d[k] > d[t] + w[j])
            {
                d[k] = d[t] + w[j];
                if (!st[k])
                {
                    q[++ tt] = k;
                    int u = tt;
                    while (u / 2 && d[q[u / 2]] > d[q[u]])
                    {
                        heap_swap(u / 2, u, q);
                        u /= 2;
                    }
                }
            }
        }
    }

    return d[t];
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int u, v, weight;
        scanf("%d%d%d", &u, &v, &weight);
        add(u, v, weight);
        add(v, u, weight);
    }
    printf("%d\n", dijkstra());
    return 0;
}

由于题目没有要求不使用 STL 容器，也可以使用 STL 中的 priority_queue 来实现堆优化 Dijkstra 算法。