#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];struct Node{ int d, u; bool operator< (const Node& t) const { return d > t.d; }};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; priority_queue<Node> q; q.push({0, s}); while (q.size()) { auto t = q.top(); q.pop(); int u = t.u; if (st[u]) continue; st[u] = true; for (int j = h[u]; j != -1; j = ne[j]) { int k = e[j]; if (d[k] > d[u] + w[j]) { d[k] = d[u] + w[j]; if (!st[k]) q.push({d[k], k}); } } } 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容器来实现上述代码的示例：

#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];

struct Node{
    int d, u;
    bool operator< (const Node& t) const
    {
        return d > t.d;
    }
};

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

void dijkstra(){
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    Node t = {0, s};
    for (int i = 0; i < n; i ++ )
    {
        int u = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (u == -1 || d[u] > d[j]))
                u = j;
        st[u] = true;
        for (int j = h[u]; j != -1; j = ne[j])
        {
            int k = e[j];
            if (d[k] > d[u] + w[j])
            {
                d[k] = d[u] + w[j];
            }
        }
    }
}

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);
    }
    dijkstra();
    printf("%d\n", d[t]);
    return 0;
}

在这个实现中，我们使用一个数组 st 来记录每个节点是否已经确定了最短路，使用一个数组 d 来记录每个节点当前的最短路。首先将起点 s 的 d 值设置为0，然后从未确定最短路的节点中选择 d 值最小的节点 u，将其确定为最短路，并更新其相邻节点的 d 值。重复这个过程，直到所有节点的最短路都已经确定。最后输出终点 t 的 d 值即可。

需要注意的是，由于最小堆在 STL 中的实现使用了比较复杂的数据结构，因此在这个实现中我们直接使用了一个结构体来表示堆中的元素，并手动实现了比较运算符。