$Floyd$ 算法

依次枚举中心点更新最短距离

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;int n,m;
vector<vector<int>> adj,pre;//回溯路径
vector<int> get_path(int s,int e){vector<int> path;if (adj[s][e]==INF) return {};int cur = e;while (1){path.push_back(cur);if (cur==s) break;cur = pre[s][cur];}reverse(path.begin(),path.end());return path;
}void solve(){cin >> n >> m;adj = vector<vector<int>>(n,vector<int>(n,INF));pre = vector<vector<int>>(n,vector<int>(n,-1));for (int i=0;i<m;i++){int u,v,w;cin >> u >> v >> w;u--,v--;adj[u][v] = adj[v][u] = w;pre[u][v] = u;pre[v][u] = v;}for (int i=0;i<n;i++){adj[i][i] = 0;pre[i][i] = i;}for (int k=0;k<n;k++){for (int i=0;i<n;i++){if (adj[i][k]==INF) continue;for (int j=0;j<n;j++){if (adj[k][j]==INF) continue;if (adj[i][k]+adj[k][j] < adj[i][j]){adj[i][j] = adj[i][k]+adj[k][j];pre[i][j] = pre[k][j];}}}}for (int i=0;i<n;i++){for (int j=0;j<n;j++){cout << adj[i][j];if (j==n-1) cout << '\n';else cout << ' ';}}
}int main(){ios::sync_with_stdio(false);cin.tie(0);solve();return 0;
}