【題目來源】
https://www.luogu.com.cn/problem/B3647

【題目描述】
給出一張由 n 個點 m 條邊組成的無向圖。
求出所有點對 (i,j) 之間的最短路徑。

【輸入格式】
第一行為兩個整數 n，m，分別代表點的個數和邊的條數。
接下來 m 行，每行三個整數 u，v，w，代表 u，v 之間存在一條邊權為 w 的邊。

【輸出格式】
輸出 n 行每行 n 個整數。
第 i 行的第 j 個整數代表從 i 到 j 的最短路徑。

【輸入樣例】
4 4
1 2 1
2 3 1
3 4 1
4 1 1

【輸出樣例】
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

【說明/提示】
對于 100% 的數據，n≤100，m≤4500，任意一條邊的權值 w 是正整數且 1?w?1000。
數據中可能存在重邊。

【算法分析】
● Floyd 算法?（又稱 Floyd-Warshall 算法）是一種用于求解?所有頂點對之間最短路徑?的動態規劃算法。它適用于?帶權有向圖或無向圖?，可以處理?正權邊和負權邊?（但不能有負權環）。

●?本題數據中可能存在重邊，若不處理，會有一個樣例不過。
若有重邊，處理方法是只保留權值最小的那條邊。代碼如下：

while(m--) {cin>>a>>b>>c;e[a][b]=min(e[a][b],c); //e[a][b]=c;e[b][a]=min(e[b][a],c); //e[b][a]=c;
}

●?若 e[i][i]<0，則存在負權環。

【算法代碼】

#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;
int e[100][100];
int a,b,c;
int n,m;int main() {cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(i==j) e[i][j]=0;else e[i][j]=inf;}}while(m--) {cin>>a>>b>>c;e[a][b]=min(e[a][b],c); //e[a][b]=c;e[b][a]=min(e[b][a],c); //e[b][a]=c;}for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {cout<<e[i][j]<<" ";}cout<<endl;}return 0;
}/*
in:
4 4
1 2 1
2 3 1
3 4 1
4 1 1out:
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
*/

【參考文獻】
https://blog.csdn.net/ahalei/article/details/22038539
https://www.cnblogs.com/CLGYPYJ/p/17586069.html
?