#include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int N = 1000010, M = 2000010;const int INF = 0x3f3f3f3f;int n, m, s, t;int h[N], e[M], ne[M], w[M], idx; // 邻接表存图int dist[N]; // 存储起点到各个点的最短距离bool st[N]; // 存储每个点的最短路是否已经确定int cnt[N]; // 存储每个点进队的次数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; queue<int> q; q.push(s); st[s] = true; while (q.size()) { int t = q.front(); q.pop(); 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] cnt[j] = cnt[t] + 1; if (cnt[j] >= n) // 如果存在正环，直接返回 false return false; if (!st[j]) // 如果 j 还没在队列中 { q.push(j); st[j] = true; } } } } 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;}不用queue的STL实现这个代码

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

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010, M = 2000010;
const int INF = 0x3f3f3f3f;

int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx; // 邻接表存图
int dist[N]; // 存储起点到各个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
int cnt[N]; // 存储每个点进队的次数
int q[N]; // 手写队列

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;
    int hh = 0, tt = 0;
    q[tt ++ ] = s;
    st[s] = true;
    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]
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) // 如果存在正环，直接返回 false
                    return false;
                if (!st[j]) // 如果 j 还没在队列中
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    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;
}

在这里我们手写了一个队列 `q`，并使用两个指针 `hh` 和 `tt` 分别指向队列头和队列尾。需要注意的是，在向队列尾添加元素时，如果队列满了，则 `tt` 需要回到队列头部，即 `tt = 0`。在遍历时，需要判断 `hh` 是否已经到达队列尾部，如果是，则需要回到队列头部，即 `hh = 0`。