题意理解
给定 nnn 个点 mmm 条边的有向图，可能存在负权边、重边、自环。求所有点对之间的最短路，若存在负环则输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
Floyd-Warshall 算法
由于存在负权边，不能用 Dijkstra。本题 n≤500n \leq 500n≤500，适合使用 Floyd 算法。
算法核心思想：
设 dis[i][j]dis[i][j]dis[i][j] 表示从 iii 到 jjj 的最短距离。枚举中转点 kkk，尝试用 i→k→ji \to k \to ji→k→j 更新 i→ji \to ji→j：
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])dis[i][j] = \min(dis[i][j], dis[i][k] + dis[k][j]) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
负环检测：
Floyd 结束后，若存在 dis[i][i]<0dis[i][i] < 0dis[i][i]<0，说明存在负环（从 iii 出发绕一圈回到 iii 距离为负）。
注意事项：
* 重边取最小值
* 自环若为负则直接判定负环，否则忽略（dis[i][i]=0dis[i][i] = 0dis[i][i]=0）
* 不可达用 10910^9109 表示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
