网站收录没了,深圳住建局竣工备案查询官网,ui设计师需要掌握的技能,常见的erp系统目录 1 基础知识2 模板3 工程化 1 基础知识
floyd算法的时间复杂度为O(n^3)#xff0c;它用来解决多源最短路问题。它的原理是基于动态规划。
floyd算法的关键步骤#xff1a;
k从1到n。i从1到n。j从1到n#xff0c;d[i][j] min(d[i][j], d[i][k] d[k][j])。经过上述三… 目录 1 基础知识2 模板3 工程化 1 基础知识
floyd算法的时间复杂度为O(n^3)它用来解决多源最短路问题。它的原理是基于动态规划。
floyd算法的关键步骤
k从1到n。i从1到n。j从1到nd[i][j] min(d[i][j], d[i][k] d[k][j])。经过上述三重循环之后数组d即是任意两个结点之间的最短距离。
2 模板
初始化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;// 算法结束后d[a][b]表示a到b的最短距离
void floyd()
{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]);
}3 工程化
题目1求两两结点之间的最短距离。
#include iostreamusing namespace std;const int N 210;
int n, m, q;
int d[N][N];int main() {cin n m q;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] 0x3f3f3f3f;}}int a, b, c;while (m--) {cin a b c;d[a][b] min(d[a][b], c);}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]);}}}while (q--) {cin a b;if (d[a][b] 0x3f3f3f3f / 2) cout impossible endl;else cout d[a][b] endl;}return 0;
}
