题目连接：点击打开链接
解题思路：
全源最短路
完整代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <climits>using namespace std;int n , m;const int maxn = 1111;const int INF = 1000000000;int d[maxn][maxn];void init(int n){for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j <= n ; j ++){if(i == j) d[i][j] = 0;else d[i][j] = INF;}}void solve(){for(int k = 1 ; k <= n ; k ++){for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);}}}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++)printf("%d%s" , d[i][j] , j == n ? "\n" : " ");}}int main(){#ifdef DoubleQfreopen("in.txt" , "r" , stdin);#endif // DoubleQwhile(cin >> n >> m){int u , v , len;init(n);for(int i = 0 ; i < m ; i ++){cin >> u >> v >> len;if(d[u][v] > len && u != v){d[u][v] = len;d[v][u] = len;}}solve();}}
，何愁没有快乐的泉溪在歌唱，何愁没有快乐的鲜花绽放！
