#include <iostream>#include <cstring>#include <queue>#define N 2005#define INF 1e18using namespace std;typedef long long ll;typedef pair<ll, int> P;int n, m, s, t;bool vis[N];ll dist[N];vector<P> G[N];void dijkstra(int s) { priority_queue<P, vector<P>, greater<P> > que; memset(vis, false, sizeof(vis)); fill(dist, dist + N, INF); dist[s] = 0; que.push(P(0, s)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(vis[v]) continue; vis[v] = true; for(int i = 0; i < G[v].size(); i++) { int u = G[v][i].second; ll d = G[v][i].first; if(dist[u] > dist[v] + d) { dist[u] = dist[v] + d; que.push(P(dist[u], u)); } } }}int main() { cin >> n >> m >> s >> t; for(int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; G[a].push_back(P(c, b)); G[b].push_back(P(c, a)); } dijkstra(s); cout << dist[t] << endl; return 0;}不使用queue的STL实现这个代码

以下是不使用 STL 的 queue 实现的代码，使用手写堆来代替 queue，原理是相同的：

#include <iostream>
#include <cstring>
#define N 2005
#define INF 1e18

using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

int n, m, s, t;
bool vis[N];
ll dist[N];
P heap[N];
int heap_size = 0;
int idx[N];

void push(P x) {
    int i = ++heap_size;
    while(i != 1 && heap[i / 2].first > x.first) {
        heap[i] = heap[i / 2];
        idx[heap[i].second] = i;
        i /= 2;
    }
    heap[i] = x;
    idx[x.second] = i;
}

void pop() {
    P x = heap[heap_size--];
    int i = 1, j = 2;
    while(j <= heap_size) {
        if(j < heap_size && heap[j].first > heap[j + 1].first) j++;
        if(heap[j].first >= x.first) break;
        heap[i] = heap[j];
        idx[heap[i].second] = i;
        i = j; j *= 2;
    }
    heap[i] = x;
    idx[x.second] = i;
}

void up(P x) {
    int i = idx[x.second];
    while(i != 1 && heap[i / 2].first > x.first) {
        heap[i] = heap[i / 2];
        idx[heap[i].second] = i;
        i /= 2;
    }
    heap[i] = x;
    idx[x.second] = i;
}

void dijkstra(int s) {
    memset(vis, false, sizeof(vis));
    fill(dist, dist + N, INF);
    dist[s] = 0; push(P(0, s));
    while(heap_size > 0) {
        P p = heap[1]; pop();
        int v = p.second;
        if(vis[v]) continue;
        vis[v] = true;
        for(int i = 0; i < G[v].size(); i++) {
            int u = G[v][i].second;
            ll d = G[v][i].first;
            if(dist[u] > dist[v] + d) {
                dist[u] = dist[v] + d;
                if(idx[u] == 0) push(P(dist[u], u));
                else up(P(dist[u], u));
            }
        }
    }
}

int main() {
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        G[a].push_back(P(c, b));
        G[b].push_back(P(c, a));
    }
    dijkstra(s);
    cout << dist[t] << endl;
    return 0;
}

这个代码相比前面的代码更加底层，可读性稍差，但是也实现了相同的算法。