网站建设公司好吗,专业网站公司,怎么用h5网站做动效,武冈 网站建设【模板】Floyd
题目描述
给出一张由 n n n 个点 m m m 条边组成的无向图。
求出所有点对 ( i , j ) (i,j) (i,j) 之间的最短路径。
输入格式
第一行为两个整数 n , m n,m n,m#xff0c;分别代表点的个数和边的条数。
接下来 m m m 行#xff0c;每行三个整数 u …【模板】Floyd
题目描述
给出一张由 n n n 个点 m m m 条边组成的无向图。
求出所有点对 ( i , j ) (i,j) (i,j) 之间的最短路径。
输入格式
第一行为两个整数 n , m n,m n,m分别代表点的个数和边的条数。
接下来 m m m 行每行三个整数 u , v , w u,v,w u,v,w代表 u , v u,v u,v 之间存在一条边权为 w w w 的边。
输出格式
输出 n n n 行每行 n n n 个整数。
第 i i i 行的第 j j j 个整数代表从 i i i 到 j j j 的最短路径。
样例 #1
样例输入 #1
4 4
1 2 1
2 3 1
3 4 1
4 1 1样例输出 #1
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0提示
对于 100 % 100\% 100% 的数据 n ≤ 100 n \le 100 n≤100 m ≤ 4500 m \le 4500 m≤4500任意一条边的权值 w w w 是正整数且 1 ⩽ w ⩽ 1000 1 \leqslant w \leqslant 1000 1⩽w⩽1000。
数据中可能存在重边。
#includebits/stdc.h
using namespace std;
#define ll long long
const ll INF 0x3f3f3f3f;
const int N 1e210;
ll dis[N][N];
int n,m;
int main(){cinnm;for(int i1;in;i)for(int j1;jn;j){if(ij)dis[i][j]0;else dis[i][j]INF;}int v1,v2;ll w;for(int i0;im;i){cinv1v2w;
// dis[v1][v2]dis[v2][v1]w;//取重边时较小的边 dis[v2][v1]dis[v1][v2]min(dis[v1][v2],w);
// dis[v2][v1]min(dis[v2][v1],w);}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if((i!j)(i!k)(j!k))dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}}for(int i1;in;i){for(int j1;jn;j){if(j1)cout ;coutdis[i][j];}coutendl; }
}
