spfa任意两点间最短路径

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
#define INF 0x3f3f3f3f;
const int N = 3000;
int n, m;
int g[N][N], dist[N];
bool st[N];
queue<int>q;
void spfa(int start) {
    st[start] = true;
    dist[start] = 0;
    q.push(start);
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = 1; i <= n; i++) {
            if (dist[i] > dist[t] + g[t][i])
            {
                dist[i] = dist[t] + g[t][i];
                if (st[i] == false)
                {
                    q.push(i);
                    st[i] = true;
                }
            }

        }
    }
}
int main() {
    int start, end;
    cin >> n >> m;
    cout << "请输入起点和终点" << endl;
    cin >> start >> end;
    memset(g, 0x3f, sizeof g);
    memset(dist, 0x3f, sizeof dist);
    int a, b, c;
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }
    spfa(start);
    cout << "最短路径为" << dist[end];
    return 0;
}