题目描述
思路解析动画文字版
记住「中转点 k 放最外层,dist[i][k]+dist[k][j] 更短就松弛」,下面逐帧套它。
先建一张 4×4 的距离表 dist[i][j] = 城市 i 到 j 的最短距离。对角线(自己到自己)填 0(绿),其余全填 ∞ 表示「还不知道怎么走」。
把每条边 (a,b,w) 填进去:dist[a][b]=dist[b][a]=w。比如 (0,1,3) 让 dist[0][1]=dist[1][0]=3。现在表里(紫)只有直接相连的距离,不直连的还是 ∞。
第 0 轮:允许所有路径经过中转点城市 0。逐个看 dist[i][j] 能不能借道 0 变短,也就是比较 dist[i][0] + dist[0][j] 和 dist[i][j]。第 0 行和第 0 列(蓝)就是这一轮的「桥」。
这一轮借道城市 0 没找到任何更短的路(城市 0 帮不上忙或已是最优),dist 表保持不变。
第 1 轮:允许所有路径经过中转点城市 1。逐个看 dist[i][j] 能不能借道 1 变短,也就是比较 dist[i][1] + dist[1][j] 和 dist[i][j]。第 1 行和第 1 列(蓝)就是这一轮的「桥」。
城市 0 到 2:原来是 ∞,但「0→1→2」只要 3 + 1 = 4,更短!更新 dist[0][2] = 4(紫)。两个蓝格就是借的桥 dist[0][1] 和 dist[1][2]。
城市 0 到 3:原来是 ∞,但「0→1→3」只要 3 + 4 = 7,更短!更新 dist[0][3] = 7(紫)。两个蓝格就是借的桥 dist[0][1] 和 dist[1][3]。
城市 2 到 0:原来是 ∞,但「2→1→0」只要 1 + 3 = 4,更短!更新 dist[2][0] = 4(紫)。两个蓝格就是借的桥 dist[2][1] 和 dist[1][0]。
城市 3 到 0:原来是 ∞,但「3→1→0」只要 4 + 3 = 7,更短!更新 dist[3][0] = 7(紫)。两个蓝格就是借的桥 dist[3][1] 和 dist[1][0]。
第 2 轮:允许所有路径经过中转点城市 2。逐个看 dist[i][j] 能不能借道 2 变短,也就是比较 dist[i][2] + dist[2][j] 和 dist[i][j]。第 2 行和第 2 列(蓝)就是这一轮的「桥」。
城市 0 到 3:原来是 7,但「0→2→3」只要 4 + 1 = 5,更短!更新 dist[0][3] = 5(紫)。两个蓝格就是借的桥 dist[0][2] 和 dist[2][3]。
城市 1 到 3:原来是 4,但「1→2→3」只要 1 + 1 = 2,更短!更新 dist[1][3] = 2(紫)。两个蓝格就是借的桥 dist[1][2] 和 dist[2][3]。
城市 3 到 0:原来是 7,但「3→2→0」只要 1 + 4 = 5,更短!更新 dist[3][0] = 5(紫)。两个蓝格就是借的桥 dist[3][2] 和 dist[2][0]。
城市 3 到 1:原来是 4,但「3→2→1」只要 1 + 1 = 2,更短!更新 dist[3][1] = 2(紫)。两个蓝格就是借的桥 dist[3][2] 和 dist[2][1]。
第 3 轮:允许所有路径经过中转点城市 3。逐个看 dist[i][j] 能不能借道 3 变短,也就是比较 dist[i][3] + dist[3][j] 和 dist[i][j]。第 3 行和第 3 列(蓝)就是这一轮的「桥」。
这一轮借道城市 3 没找到任何更短的路(城市 3 帮不上忙或已是最优),dist 表保持不变。四轮都跑完,dist 已是全源最短路。
数城市 0 这一行:到其它城市的最短距离里,≤ 4 的有 2 个(绿),分别是 1(3)、2(4)。这就是城市 0 的「阈值内邻居数」。
数城市 1 这一行:到其它城市的最短距离里,≤ 4 的有 3 个(绿),分别是 0(3)、2(1)、3(2)。这就是城市 1 的「阈值内邻居数」。
数城市 2 这一行:到其它城市的最短距离里,≤ 4 的有 3 个(绿),分别是 0(4)、1(1)、3(1)。这就是城市 2 的「阈值内邻居数」。
数城市 3 这一行:到其它城市的最短距离里,≤ 4 的有 2 个(绿),分别是 1(2)、2(1)。这就是城市 3 的「阈值内邻居数」。
把四座城市的邻居数排开:城市 0 有 2 个,城市 1 有 3 个,城市 2 有 3 个,城市 3 有 2 个。最少是 2 个,城市 0 和城市 3 并列。题目要求并列时取编号最大的,所以答案是城市 3。
最终答案:城市 3。它在阈值 4 内只有 2 个近邻、并列时编号最大。回头看:整道题的核心就是先用 Floyd 把任意两城的最短距离一次性算全,再简单数一数即可。
边界:无边图取大编号;有重边取最小权;阈值极大时比可达数。
两个追问:点少要全源距离首选 Floyd;它还能判负环、求传递闭包。
参考代码
from typing import Listclass Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: INF = 10**15 dist = [[INF] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for a, b, w in edges: dist[a][b] = dist[b][a] = min(dist[a][b], w) for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] best_city, best_count = -1, 10**9 for i in range(n): cnt = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold) if cnt <= best_count: best_count = cnt best_city = i return best_city复杂度
- 时间：O(n³)，Floyd 三重循环 n×n×n;最后逐城计数是 O(n²),被三次方主导
- 空间：O(n²)，一张 n×n 的 dist 距离表
易错点
面试追问把动画讲成自己的话
追问为什么这题用 Floyd 而不是对每个点跑一次 Dijkstra?
追问Floyd 还能解决什么问题?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
重新规划路线
LeetCode 1466 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题