T3-2 全源最短路

题意理解

给定 $n$ 个点 $m$ 条边的有向图，可能存在负权边、重边、自环。求所有点对之间的最短路，若存在负环则输出 $-1$。

---

思路分析

Floyd-Warshall 算法

由于存在负权边，不能用 Dijkstra。本题 $n \leq 500$，适合使用 Floyd 算法。

算法核心思想：

设 $dis[i][j]$ 表示从 $i$ 到 $j$ 的最短距离。枚举中转点 $k$，尝试用 $i \to k \to j$ 更新 $i \to j$：

$$dis[i][j] = \min(dis[i][j], dis[i][k] + dis[k][j])$$

负环检测：

Floyd 结束后，若存在 $dis[i][i] < 0$，说明存在负环（从 $i$ 出发绕一圈回到 $i$ 距离为负）。

注意事项：

• 重边取最小值
• 自环若为负则直接判定负环，否则忽略（$dis[i][i] = 0$）
• 不可达用 $10^9$ 表示

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;              // 最大点数
const long long INF = 1e9;         // 无穷大

int n, m;                          // 点数、边数
long long dis[MAXN][MAXN];         // dis[i][j]表示i到j的最短距离

int main() {
    cin >> n >> m;                 // 读入点数和边数
    
    for (int i = 1; i <= n; i++) {          // 初始化距离矩阵
        for (int j = 1; j <= n; j++) {
            if (i == j) dis[i][j] = 0;      // 自己到自己距离为0
            else dis[i][j] = INF;           // 其他初始化为无穷大
        }
    }
    
    for (int i = 0; i < m; i++) {  // 读入m条边
        int u, v;                  // 边的起点和终点
        long long w;               // 边的权值
        cin >> u >> v >> w;        // 读入边的信息
        if (u == v) {              // 自环
            if (w < 0) {           // 负权自环直接是负环
                cout << -1 << endl;
                return 0;
            }
        } else {                   // 非自环
            dis[u][v] = min(dis[u][v], w);  // 重边取最小值
        }
    }
    
    for (int k = 1; k <= n; k++) {          // 枚举中转点k
        for (int i = 1; i <= n; i++) {      // 枚举起点i
            for (int j = 1; j <= n; j++) {  // 枚举终点j
                if (dis[i][k] < INF && dis[k][j] < INF) {  // 防止溢出
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  // 尝试更新
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) { // 检测负环
        if (dis[i][i] < 0) {       // 自己到自己距离为负说明有负环
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int i = 1; i <= n; i++) {          // 输出距离矩阵
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << " ";         // 数字之间用空格分隔
            cout << dis[i][j];              // 输出i到j的最短距离
        }
        cout << endl;                       // 换行
    }
    
    return 0;
}