106 lines
3.7 KiB
C++
106 lines
3.7 KiB
C++
/*
|
||
* @Author: e2hang 2099307493@qq.com
|
||
* @Date: 2025-12-12 13:49:24
|
||
* @LastEditors: e2hang 2099307493@qq.com
|
||
* @LastEditTime: 2025-12-12 13:50:06
|
||
* @FilePath: \undefinedd:\code\Git-DataStructureAlgorithms\模板\图\Floyd最短路径.cpp
|
||
* @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
|
||
*/
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
using ll = long long;
|
||
const ll INF = (ll)4e18; // 足够大的无穷（要确保 INF + INF 不溢出）
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
int n, m;
|
||
// 输入: n = 顶点数, m = 边数
|
||
// 顶点编号假定为 1..n
|
||
if (!(cin >> n >> m)) return 0;
|
||
|
||
// 距离矩阵 d，和 next 矩阵用于路径恢复
|
||
vector<vector<ll>> d(n+1, vector<ll>(n+1, INF));
|
||
vector<vector<int>> nxt(n+1, vector<int>(n+1, -1));
|
||
|
||
// 初始化：距离为 INF，自身为0
|
||
for (int i = 1; i <= n; ++i) {
|
||
d[i][i] = 0;
|
||
nxt[i][i] = i; // 可选：表示到自身的下一跳是自己
|
||
}
|
||
|
||
// 读边（有向图）。若是无向图，请同时赋值两个方向
|
||
// 若图中可能有多条边，取较小的权重
|
||
for (int i = 0; i < m; ++i) {
|
||
int u, v;
|
||
long long w;
|
||
cin >> u >> v >> w;
|
||
if (w < d[u][v]) {
|
||
d[u][v] = w;
|
||
nxt[u][v] = v; // 初始从 u 到 v 的下一跳是 v
|
||
}
|
||
}
|
||
|
||
// Floyd–Warshall 主循环
|
||
for (int k = 1; k <= n; ++k) {
|
||
for (int i = 1; i <= n; ++i) {
|
||
if (d[i][k] == INF) continue; // 剪枝：i->k 不可达就跳过
|
||
for (int j = 1; j <= n; ++j) {
|
||
if (d[k][j] == INF) continue; // 剪枝：k->j 不可达就跳过
|
||
ll through = d[i][k] + d[k][j];
|
||
if (through < d[i][j]) {
|
||
d[i][j] = through;
|
||
nxt[i][j] = nxt[i][k]; // 路径恢复：先走 i->k 的第一步
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
// 检测负权回路：若任何 d[i][i] < 0 表示存在负环（经过该顶点的路径可以无限变小）
|
||
bool has_negative_cycle = false;
|
||
for (int i = 1; i <= n; ++i) {
|
||
if (d[i][i] < 0) {
|
||
has_negative_cycle = true;
|
||
break;
|
||
}
|
||
}
|
||
|
||
// 输出示例（可按需修改）
|
||
if (has_negative_cycle) {
|
||
cout << "Graph contains a negative-weight cycle reachable from some vertices.\n";
|
||
// 竞赛中通常要求你输出并退出或按题意处理
|
||
} else {
|
||
// 示例：输出任意两点间的最短距离矩阵（不可达输出 INF 表示）
|
||
for (int i = 1; i <= n; ++i) {
|
||
for (int j = 1; j <= n; ++j) {
|
||
if (d[i][j] >= INF/4) cout << "INF";
|
||
else cout << d[i][j];
|
||
if (j < n) cout << ' ';
|
||
}
|
||
cout << '\n';
|
||
}
|
||
}
|
||
|
||
// 示例：如何恢复一条具体的最短路径（从 u 到 v）
|
||
auto get_path = [&](int u, int v) -> vector<int> {
|
||
vector<int> path;
|
||
if (nxt[u][v] == -1) return path; // 不可达
|
||
int cur = u;
|
||
path.push_back(cur);
|
||
while (cur != v) {
|
||
cur = nxt[cur][v];
|
||
// 防止无限循环（理论上 nxt 应该使得路径在 n 步内结束）
|
||
if (cur == -1) return vector<int>();
|
||
path.push_back(cur);
|
||
if ((int)path.size() > n+5) return vector<int>(); // 保护措施：出现异常则返回空
|
||
}
|
||
return path;
|
||
};
|
||
|
||
// （可选）读取查询并输出路径示例：
|
||
// int q; cin >> q; while(q--){ int u,v; cin>>u>>v; auto p=get_path(u,v); ... }
|
||
|
||
return 0;
|
||
}
|