北京网站策划服务,网站首次打开速度慢wordpress,最权威的品牌排行榜网站,网站建设时间计划书【模板】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。
数据中可能存在重边。
代码实现
#include stdio.h
void floyd(); // Floyd算法
#define MAX 10000
#define INF 0x3f3f3f3f // 无穷大
int n, m;
int g[MAX][MAX];int main()
{int i, j, u, v, w;scanf(%d %d, n, m); // 输入点的个数和边的条数for (i 1; i n; i) // 初始化图的邻接矩阵{for (j 1; j n; j){// 对角线上的元素为0其他元素为无穷大if (i j){g[i][j] 0;}else{g[i][j] INF;}}}for (i 0; i m; i){scanf(%d %d %d, u, v, w);if (g[u][v] w) // 由于可能存在重边我们需要保留权值最小的那条边{g[u][v] w;g[v][u] w;}}floyd(); // 执行Floyd算法for (i 1; i n; i){for (j 1; j n; j){printf(%d , g[i][j]); }printf(\n);}return 0;
}void floyd()
{int i, j, k; // i和j是起始和结束节点k是中间节点for (k 1; k n; k){for (i 1; i n; i){for (j 1; j n; j){// 如果通过k节点的路径比当前i到j的路径短那么更新g[i][j]if (g[i][k] ! INF g[k][j] ! INF g[i][j] g[i][k] g[k][j]){g[i][j] g[i][k] g[k][j];}}}}
}无向图的最小环问题
题目描述
给定一张无向图求图中一个至少包含 3 3 3 个点的环环上的节点不重复并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中你需要输出最小的环的边权和。若无解输出 No solution.。
输入格式
第一行两个正整数 n , m n,m n,m 表示点数和边数。
接下来 m m m 行每行三个正整数 u , v , d u,v,d u,v,d表示节点 u , v u,v u,v 之间有一条长度为 d d d 的边。
输出格式
输出边权和最小的环的边权和。若无解输出 No solution.。
样例 #1
样例输入 #1
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20样例输出 #1
61提示
样例解释一种可行的方案 1 − 3 − 5 − 2 − 1 1-3-5-2-1 1−3−5−2−1。
对于 20 % 20\% 20% 的数据 n , m ≤ 10 n,m \leq 10 n,m≤10。
对于 60 % 60\% 60% 的数据 m ≤ 100 m\leq 100 m≤100。
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 100 1\le n\leq 100 1≤n≤100 1 ≤ m ≤ 5 × 1 0 3 1\le m\leq 5\times 10^3 1≤m≤5×103 1 ≤ d ≤ 1 0 5 1 \leq d \leq 10^5 1≤d≤105。
无解输出包括句号。
代码
