网站建设公司专业网站开发需求,怎么在后台设计网站,福州专业建站,软件开发兼职平台知识概览 Floyd算法适合解决多源汇最短路问题#xff0c;其中源点是起点#xff0c;汇点是终点。时间复杂度是。 例题展示
题目链接
活动 - AcWing 系统讲解常用算法与数据结构#xff0c;给出相应代码模板#xff0c;并会布置、讲解相应的基础算法题目。https://www.acw…知识概览 Floyd算法适合解决多源汇最短路问题其中源点是起点汇点是终点。时间复杂度是。 例题展示
题目链接
活动 - AcWing 系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/856/
题解 Floyd算法基于动态规划的思想主要是三重循环先遍历ki和j的遍历顺序谁先谁后都可以。 代码
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 210, INF 1e9;int n, m, Q;
int d[N][N];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]);
}int main()
{scanf(%d%d%d, 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] INF;while (m--){int a, b, w;scanf(%d%d%d, a, b, w);d[a][b] min(d[a][b], w);}floyd();while (Q--){int a, b;scanf(%d%d, a, b);if (d[a][b] INF / 2) puts(impossible);else printf(%d\n, d[a][b]);}return 0;
} 参考资料
AcWing算法基础课
