【算法】图论——Floyd算法python

洛谷 B3647 【模板】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。

数据中可能存在重边。

---

AC_code n, m = map(int, input().split()) dp = [[float('inf')] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][i] = 0 for _ in range(m): u, v, w = map(int, input().split()) dp[u][v] = dp[v][u] = min(dp[u][v], w) for k in range(1, n + 1): for i in range(1, n + 1): for j in range(1, n + 1): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) for row in dp[1:]: print(" ".join(map(str, row[1:])))

---

实战演练

城市间的交易

AC_code n, m = map(int, input().split()) dp = [[float('inf')] * (n + 1) for _ in range(n + 1)] res = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): dp[i][i] = 0 a, p, s = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1) for i in range(1, n + 1): a[i], p[i], s[i] = map(int, input().split()) for _ in range(m): u, v, w = map(int, input().split()) dp[u][v] = dp[v][u] = min(dp[u][v], w) for k in range(1, n + 1): for i in range(1, n + 1): for j in range(1, n + 1): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) # res[i][j]表示一个城市i的物品运输到城市j的最大利润 for i in range(1, n + 1): for j in range(1, n + 1): res[i][j] = s[j] - dp[i][j] - p[i] ans = 0 for i in range(1, n + 1): cur = 0 for j in range(1, n + 1): cur = max(cur, a[i] * res[i][j]) ans += cur print(ans)

---

END 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢