LeetCode 1334. 阈值距离内邻居最少的城市
题目描述
题意分析
城市之间是双向带权道路。对每个城市，统计最短路径长度不超过
distanceThreshold的其他城市数，返回数量最少的城市；数量相同时取编号最大的。距离等于阈值也算，自身不计入邻居。
解法：Floyd 全源最短路
核心思路
[!blue]
需要知道每一对城市的最短距离，而城市数最多只有 100，可以用 Floyd 算法一次求出所有点对。
dist[start][end]表示当前允许的中转城市范围内，两城之间的最短距离；初始不允许任何中转，只保留直连边、自身距离 0 和不可达标记inf。每轮新增一个可用的中转城市
middle。最短路要么不经过它，沿用旧距离；要么经过它，拆成start到middle、middle到end两段，候选长度为两段距离之和。边权为正，最短路无需重复经过同一城市，这两种情况便覆盖了全部可能，取较小值即可。
middle必须放在最外层：处理这一轮时，两段距离才都已包含此前所有中转城市的结果。又因为dist[middle][middle] = 0，当前轮不会进一步改变通向middle或从它出发的距离，所以可以直接在二维矩阵中原地更新。任意一段不可达时不能组成路径，应先跳过。最后按编号从小到大统计邻居。
bestCount保存目前最少的邻居数，当前数量小于或等于它时都更新答案；相等也覆盖，才能让较大的编号留下。没有任何邻居的城市计数为 0，同样正常参与比较。
解题步骤
- 初始化自身零、其他不可达，写入无向边。
- 逐中间点松弛所有点对，任一段不可达则跳过。
- 统计阈值内的其他城市，按少量与大编号规则选择。
代码实现
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
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;
}
}
// 中间城市是动态规划阶段，必须先于点对枚举。
for (int middle = 0; middle < n; middle++) {
for (int start = 0; start < n; start++) {
for (int end = 0; end < n; end++) {
// 任一段不可达，就不能组成经过当前中间城市的路径。
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;
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 {
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
}
}
// 中间城市是动态规划阶段，必须先于点对枚举。
for middle := 0; middle < n; middle++ {
for start := 0; start < n; start++ {
for end := 0; end < n; end++ {
// 任一段不可达，就不能组成经过当前中间城市的路径。
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
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)$，三重循环求最短路；初始化和最终统计均为 $O(n^2)$。
- 空间复杂度：$O(n^2)$，完整距离矩阵。
关键点总结
[!green]
- 中间点维度表达允许使用的中转集合。
- 等于阈值也可达，并列数量时用后来编号覆盖。
- 题面正权路径的最短路可去掉重复城市，最多含 $n-1$ 条边，
inf = 10^9足以与真实距离区分。
易错点总结
[!yellow]
- 只比较直连边，会漏掉更便宜的绕路。
- 升序遍历却仅在严格更少时更新，会保留较小编号。
- 把带权距离当成边数，会改变可达范围。
- 将中转点放进内层只遍历一次，可能在所需子路径尚未求出时就错过更新。
- 没有排除自身，会把对角线上的距离 0 也统计进去。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 743. 网络延迟时间 | 中等 | 原题从一个源求最短距离，本题需要对每个城市统计阈值内的可达城市数。 |
| 1462. 课程表 IV | 中等 | 同样可用全源传递更新，原题维护布尔可达性，本题维护带权最短距离并按阈值统计。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！