【LeetCode】每日一题 2023_11_14 阈值距离内邻居最少的城市（Floyd 最短路算法）

刷题前唠嗑

LeetCode? 启动！！！

今天的题目也是重量级，看到这个题目的名字，看到这张图，虽然是个中等题，但感觉他一定不简单！（其实看到这个图，最短路问题已经在我脑中浮现了，ptsd 了呜呜）

题目：阈值距离内邻居最少的城市

题目链接：1334. 阈值距离内邻居最少的城市

题目描述

代码与解题思路

实话实说，不会图论，我决定直接不浪费时间

所以，B 站收藏+1，下次一定好好学习：

随机挑选一个大佬的题解 CV

func findTheCity(n int, edges [][]int, distanceThreshold int) (ans int) {
    w := make([][]int, n)
    for i := range w {
        w[i] = make([]int, n)
        for j := range w[i] {
            w[i][j] = math.MaxInt / 2 // 防止加法溢出
        }
    }
    for _, e := range edges {
        x, y, wt := e[0], e[1], e[2]
        w[x][y], w[y][x] = wt, wt
    }

    f := w
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                f[i][j] = min(f[i][j], f[i][k]+f[k][j])
            }
        }
    }

    minCnt := n
    for i, dis := range f {
        cnt := 0
        for j, d := range dis {
            if j != i && d <= distanceThreshold {
                cnt++
            }
        }
        if cnt <= minCnt { // 相等时取最大的 i
            minCnt = cnt
            ans = i
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

结语

我一定找一个时间把最近遇到的算法都学一遍，一定