Floyd利用动态规划暴力计算多源点间最短路.
通过枚举"中转站",并枚举所有可行的起点和终点,检查通过此中转站能否得到此起点终点的更短路径.O(N3).
由于其复杂度较大(因而只能处理小数据)且需要同时检查中转站的父节点和子节点,适合用邻接矩阵处理.
(带权图,边权可正可负,不存在的路径初始化为INF)
for (int k = 1; k <= n; ++k) // 中转站 for (int i = 1; i <= n; ++i) // 起点 if (i != k) for (int j = 1; j <= n; ++j) // 终点 if (i != j && j != k) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
进行Floyd处理后,dist[i][j]即表示节点 i 到节点 j 的最短距离.
不能处理有负权回路的图.
这里的每一个节点到任意一个其他节点都是有一条有向边的,存图和算距离可以在同一个数组中操作.
只需Floyd先算出任意两点间的最短路,再累加给定的序列中相邻两点的最短路即可.
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; int n, m, dist[110][110], s[10010]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d", s + i); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &dist[i][j]); for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) if (i != k) for (int j = 1; j <= n; ++j) if (i != j && j != k) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int ans = 0; for (int i = 1; i < m; i++) ans += dist[s[i]][s[i + 1]]; printf("%d\n", ans); return 0; }P2910