LeetCode 1334. 阈值距离内邻居最少的城市

Categories:

题目描述
思路分析
1. 解法一：Floyd 最短路（推荐）
相似题目

题目描述

✅ 1334. 阈值距离内邻居最少的城市

思路分析

解法一：Floyd 最短路（推荐）

核心思路：

初始化邻接矩阵，未连通设为 INF。

通过 Floyd 算法计算任意两点最短距离。

对每个城市统计可达且距离不超过阈值的邻居数，取最小且索引最大。

复杂度分析：

时间复杂度：O(n^3)。

空间复杂度：O(n^2)。

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 i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
            }
        }
        for (int[] e : edges) {
            dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        int bestCity = -1;
        int bestCnt = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] <= distanceThreshold) {
                    cnt++;
                }
            }
            if (cnt <= bestCnt) {
                bestCnt = cnt;
                bestCity = i;
            }
        }
        return bestCity;
    }
}

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
    const inf = 1_000_000_000
    dist := make([][]int, n)
    for i := 0; i < n; i++ {
        dist[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if i == j {
                dist[i][j] = 0
            } else {
                dist[i][j] = inf
            }
        }
    }
    for _, e := range edges {
        if e[2] < dist[e[0]][e[1]] {
            dist[e[0]][e[1]] = e[2]
            dist[e[1]][e[0]] = e[2]
        }
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    bestCity := -1
    bestCnt := 1 << 30
    for i := 0; i < n; i++ {
        cnt := 0
        for j := 0; j < n; j++ {
            if i != j && dist[i][j] <= distanceThreshold {
                cnt++
            }
        }
        if cnt <= bestCnt {
            bestCnt = cnt
            bestCity = i
        }
    }
    return bestCity
}

相似题目

题目	难度	考察点
743. 网络延迟时间	中等	最短路
787. K 站中转内最便宜的航班	中等	最短路
882. 细分图中的可到达节点	困难	最短路
1514. 概率最大的路径	中等	最短路
1976. 到达目的地的方案数	中等	最短路

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/12953406