LeetCode 1334. 阈值距离内邻居最少的城市
目录
题目描述
题意分析
给一张
n个点的无向带权图和一个阈值distanceThreshold，对每个城市统计「最短距离不超过阈值」的其他城市个数，返回这个数量最小的城市；如果多个城市并列最小，返回其中编号最大的那个。三个细节要在动手前钉死。第一，判定用的是最短距离而不是直接相连的边权，绕路可能比直连更短，所以必须先把两两最短距离全部算出来。第二，统计时不能把城市自己算进去，
dist[i][i] = 0一定满足阈值。第三，并列时取大编号，这条规则会直接决定后面比较运算符写<还是<=。约束是最强的信号：
2 <= n <= 100。$n^3 = 10^6$，对现代机器只是一瞬间，这等于明说「允许你把所有点对的最短距离都算出来」，不必去追求更优的渐近复杂度。边权1 <= weight <= 10^4全为正，没有负权边，也就不存在负环之类的麻烦。边界：图不保证连通，可能存在互相到不了的城市，这种城市的可达数是 0，会成为最优解；
n最小是 2，不会出现空图。另外要注意最长可能路径的量级是99 * 10^4 ≈ 10^6，远在 int 范围内，真正需要提防的是「不可达」那个哨兵值参与加法。
解法：Floyd 全源最短路
核心思路
先想暴力：以每个城市为起点各跑一次 Dijkstra 或 SPFA，
n次单源最短路就能得到全部答案。这在复杂度上完全没问题（甚至更优），但要写堆、要建邻接表，白板上代码量是 Floyd 的好几倍，而n <= 100根本不需要这份优化。换个角度：我们要的不是「某一个起点的最短路」，而是全源最短距离矩阵本身。这类需求有一个天然的动态规划刻画。
状态定义：
f[k][i][j]表示只允许使用编号小于k的城市作为中间转折点时，从i到j的最短距离。初始的f[0][i][j]就是不允许任何中转，即i与j之间的直连边权（无边则为无穷大，i == j为 0）。转移：新放开中转点
k时，i到j的最短路要么根本不经过k，要么恰好经过k一次（正权图里经过两次一定不会更短）。于是f[k+1][i][j] = min(f[k][i][j], f[k][i][k] + f[k][k][j])。降维：注意
f[k][i][k]和f[k][k][j]在第k轮里不会被改小（改它们需要用到f[k][k][k] = 0，加上去等于没变），所以第一维可以安全地原地滚动掉，得到熟悉的三重循环。这正是「中转点k必须写在最外层」的根本原因：k是 dp 的阶段维，把它挪到内层就等于打乱了 dp 的推进顺序，某些需要多次中转的路径永远算不出来。最外层跑完
k = n-1之后，dist[i][j]就是允许使用全部城市中转的真正最短距离。剩下的就是一次 $O(n^2)$ 的计数：对每个城市数一下阈值内的邻居，按「更少或并列」的规则更新答案。并列取大编号这条规则有个很省事的写法：城市编号从小到大遍历，把更新条件放宽成
count <= bestCount。相等时后来者覆盖前者，遍历结束时留下的自然是编号最大的那个，不需要额外比较编号。
解题步骤
- 初始化距离矩阵：
dist[i][i] = 0，其余全部置为一个「足够大但不会溢出」的值（这里用10^9）。用Integer.MAX_VALUE会让后面的加法溢出成负数，属于自找麻烦。- 写入边：无向图必须两个方向都赋值。写成
if (weight < dist[from][to])而不是直接赋值，是一层防御——本题保证没有重边，但同样的模板套到允许重边的题上时，只保留最短的那条才正确。- 三重循环松弛：外层
middle，中层start，内层end。循环体里先检查dist[start][middle]与dist[middle][end]是否为无穷大，是则直接跳过，避免两个哨兵值相加。- 逐城计数：对每个
city，遍历所有other，在city != other且dist[city][other] <= distanceThreshold时计数。city != other不能省，否则每个城市都会把自己算进去。- 按规则更新答案：
bestCount初值取n + 1，保证第一个城市一定能刷进去；更新条件用count <= bestCount，配合升序遍历实现「并列取大编号」。- 返回
bestCity。以
n = 4、edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]、distanceThreshold = 4走一遍（inf表示不可达）。初始矩阵按行是：
[0,3,inf,inf]、[3,0,1,4]、[inf,1,0,1]、[inf,4,1,0]。
middle = 0：城市 0 只连着 1，任何经过它的绕路都不会更短，矩阵不变。
middle = 1：dist[0][2]由inf降为3 + 1 = 4，dist[0][3]由inf降为3 + 4 = 7；dist[2][3]的候选是1 + 4 = 5，不如已有的 1，不更新。第 0 行变成[0,3,4,7]。
middle = 2：dist[0][3]的候选是dist[0][2] + dist[2][3] = 4 + 1 = 5 < 7，更新；dist[1][3]的候选是1 + 1 = 2 < 4，更新。注意dist[0][2] = 4是上一轮才算出来的，如果把middle放在内层，这条两次中转的路径就永远拼不出来。
middle = 3：所有候选都不更短，矩阵稳定为[0,3,4,5]、[3,0,1,2]、[4,1,0,1]、[5,2,1,0]。计数阶段，阈值 4：城市 0 的三个距离是 3、4、5，前两个合格，
count = 2；城市 1 是 3、1、2，全合格，count = 3；城市 2 是 4、1、1，count = 3；城市 3 是 5、2、1，后两个合格，count = 2。更新过程：
bestCount = 5起步；city = 0的 2 满足2 <= 5，记下(0, 2)；city = 1的 3 不满足3 <= 2；city = 2同理跳过；city = 3的 2 满足2 <= 2，覆盖成(3, 2)。返回 3。若把条件写成严格小于，最后一步不会覆盖，就会错误地返回 0。
代码实现
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
// 用 1e9 而不是 Integer.MAX_VALUE，留出加法余量。
int inf = 1_000_000_000;
int[][] dist = new int[n][n];
for (int start = 0; start < n; start++) {
for (int end = 0; end < n; end++) {
if (start == end) {
dist[start][end] = 0;
} else {
dist[start][end] = inf;
}
}
}
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int weight = edge[2];
// 无向图两个方向都要写；取较小值是为了兼容可能出现重边的场景。
if (weight < dist[from][to]) {
dist[from][to] = weight;
dist[to][from] = weight;
}
}
// middle 是 dp 的阶段维（允许中转的点集），必须在最外层。
for (int middle = 0; middle < n; middle++) {
for (int start = 0; start < n; start++) {
for (int end = 0; end < n; end++) {
// 任一段不可达就没有经过 middle 的路径，跳过以免哨兵值相加。
if (dist[start][middle] == inf || dist[middle][end] == inf) {
continue;
}
dist[start][end] = Math.min(
dist[start][end],
dist[start][middle] + dist[middle][end]);
}
}
}
int bestCity = -1;
// 初值取 n + 1，保证第一个城市一定能刷进去。
int bestCount = n + 1;
for (int city = 0; city < n; city++) {
int count = 0;
for (int other = 0; other < n; other++) {
if (city != other && dist[city][other] <= distanceThreshold) {
count++;
}
}
// 升序遍历 + 允许相等覆盖，等价于「并列时取编号最大者」。
if (count <= bestCount) {
bestCount = count;
bestCity = city;
}
}
return bestCity;
}
}
func findTheCity(n int, edges [][]int, distanceThreshold int) int {
// 用 1e9 而不是 math.MaxInt32，留出加法余量。
const inf = 1_000_000_000
dist := make([][]int, n)
for start := 0; start < n; start++ {
dist[start] = make([]int, n)
for end := 0; end < n; end++ {
if start == end {
dist[start][end] = 0
} else {
dist[start][end] = inf
}
}
}
for _, edge := range edges {
from, to, weight := edge[0], edge[1], edge[2]
// 无向图两个方向都要写；取较小值是为了兼容可能出现重边的场景。
if weight < dist[from][to] {
dist[from][to] = weight
dist[to][from] = weight
}
}
// middle 是 dp 的阶段维（允许中转的点集），必须在最外层。
for middle := 0; middle < n; middle++ {
for start := 0; start < n; start++ {
for end := 0; end < n; end++ {
// 任一段不可达就没有经过 middle 的路径，跳过以免哨兵值相加。
if dist[start][middle] == inf || dist[middle][end] == inf {
continue
}
if dist[start][middle]+dist[middle][end] < dist[start][end] {
dist[start][end] = dist[start][middle] + dist[middle][end]
}
}
}
}
bestCity := -1
// 初值取 n + 1，保证第一个城市一定能刷进去。
bestCount := n + 1
for city := 0; city < n; city++ {
count := 0
for other := 0; other < n; other++ {
if city != other && dist[city][other] <= distanceThreshold {
count++
}
}
// 升序遍历 + 允许相等覆盖，等价于「并列时取编号最大者」。
if count <= bestCount {
bestCount = count
bestCity = city
}
}
return bestCity
}
复杂度分析
- 时间复杂度：$O(n^3)$。三重循环各跑
n次，循环体是常数次比较与加法；建图 $O(m)$、计数 $O(n^2)$ 都被这一项吞没。n <= 100时约 $10^6$ 次基本操作，完全够用。- 空间复杂度：$O(n^2)$。距离矩阵保存任意两城之间的当前最短距离，这是 Floyd 相对「跑
n次 Dijkstra」的主要代价——后者只需要 $O(n + m)$ 的图加一维距离数组。
关键点总结
- Floyd 的三重循环有严格顺序：
middle是 dp 的阶段维，start、end只是在这一阶段内枚举点对。记住「阶段维在最外层」这一条，就再也不会写反。- 哨兵值要选可加的：无穷大用
10^9这类「大到不可能是真实答案、又小到加两次不溢出」的数，或者像本题一样在加法前显式判不可达。两者取其一即可，同时做更保险。- 并列取大编号 = 升序遍历 +
<=：把题目的 tie-break 规则翻译成比较运算符，比事后再比编号更不容易出错；若题目要求取小编号，就必须改回严格小于。- 算法选择要看数据规模：
n <= 100是在邀请你写 Floyd。同样一道题若n到 $10^5$ 而只查若干源点，正确答案就变成堆优化 Dijkstra；面试里主动报出这个分界点，比闷头写代码更有分量。- 面试视角：能把三重循环还原成
f[k][i][j]的 dp 定义并解释第一维为什么能滚动掉，是这题唯一的区分点。只会背模板的人答不上「为什么k在最外层」。
易错点总结
- 无穷大用
Integer.MAX_VALUE且不判不可达：n = 3、edges = [[0,1,1]]、阈值 1 时，dist[0][1] + dist[1][2]溢出成负数，dist[0][2]被更新为一个负值，城市 2 凭空多出一个「可达邻居」，答案从 2 变成 1。- 更新条件写成
count < bestCount：上面走查的n = 4用例里，城市 0 和城市 3 的可达数都是 2，严格小于不会让 3 覆盖 0，返回 0 而不是 3。- 只写单向边：
edges = [[0,1,3]]时只赋dist[0][1]，dist[1][0]仍是无穷大，城市 1 的可达数少算一个，很容易让它被误判成最优解。- 把
middle写在内层：对链状图0-1-2-3（每条边权 1）、阈值 3，dist[0][3]需要先由middle = 1算出dist[0][2]、再由middle = 2拼出来。middle在内层时这条两跳中转路径拼不出来，dist[0][3]停在无穷大，城市 0 的可达数被低估成 2。bestCount初值取 0 或-1：任何城市的count都不满足count <= 0，循环走完bestCity仍是-1，直接返回非法编号。初值必须大于任何可能的count，即至少n。- 统计时漏掉
city != other：dist[i][i] = 0必然通过阈值，每个城市的count都多 1，虽然大小关系没变，但一旦题目改成「返回可达数本身」就立刻错，且这类隐性偏移在调试时极难定位。- 阈值判断写成
<：走查用例里城市 0 到城市 2 的距离恰好是 4，等于阈值。用严格小于会把它排除，城市 0 的count变成 1 并成为唯一最小值，返回 0。- 把阈值当成边数上限：用无权 BFS 数「几步之内」而不是累加边权，走查用例中城市 0 到城市 3 是 3 条边但距离为 5，按边数会被错误计入阈值内。
- 忘记
dist[i][i] = 0：矩阵全填无穷大时，middle == start或middle == end的那些转移全被跳过，虽然本题的最短路结果碰巧不受影响，但一旦后续逻辑读取dist[i][i]（例如判负环、算环路）就会得到错误的语义。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 743. 网络延迟时间 | 中等 | 单源最短路后取全体最大值，有向图，点数大时必须换成堆优化 Dijkstra |
| 787. K 站中转内最便宜的航班 | 中等 | 状态多一维「已用中转次数」，用 Bellman-Ford 按轮松弛，不能直接套 Floyd |
| 1462. 课程表 IV | 中等 | Floyd 的布尔版传递闭包，转移从 min 加法换成 or 与 and
|
| 1631. 最小体力消耗路径 | 中等 | 路径代价是「最大单边」而非边权之和，松弛式里的加法要换成取最大值 |
| 778. 水位上升的泳池中游泳 | 困难 | 同为瓶颈路，但更常见的写法是二分水位加连通性判断，绕开最短路 |
| 399. 除法求值 | 中等 | 边权是比值，路径合成用乘法而非加法，可用 Floyd 也可用带权并查集 |
| 505. 迷宫 II | 中等 | 图是隐式的，边由「滚到墙为止」定义，需要先把网格翻译成带权图 |