1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

題目
思路：

• 要找的點是可到達的點的距離在 threshold 裡的那些點，所以要找的是最短距離，因為只要最短距離可以在 threshold 內，那它就是可到達的點
• 用 Floyd-Warshall’s algorithm 找到所有點之間的最小距離
  • k 是 i 到 j 之間的任意點。比較 i -> j 經過所有 k 的距離，最小的即為 i -> j 的最短距離。
  • Question:
    if the path is i -> 2 -> 1 -> j and the iteration consider k == 1 first. But the dist[i][1] not yet populated and still have value of float('inf'). It will have the actual value until k == 2.
    • Answer from ChatGPT:
      • You’ve identified a key aspect of the Floyd-Warshall algorithm’s iterative process. The algorithm relies on the gradual building of shortest paths through each possible intermediate vertex, and the order of considering vertices (the k values) doesn’t prevent it from eventually finding the shortest paths.
      • In your example, even if k == 1 is considered first and the direct path i -> 1 or 1 -> j isn’t the shortest, the algorithm might not immediately find the shortest path i -> 2 -> 1 -> j. However, when k == 2 is later considered, the algorithm will then take into account paths through 2, updating the shortest path calculations accordingly.
      • The crux of the Floyd-Warshall algorithm is that by the time all vertices have been iteratively considered as potential intermediate steps, it will have computed the shortest paths between all pairs of vertices, considering all possible intermediate vertices and paths.
• 比較每個點在 threshold 內可達的點的個數，找出最小的＆有最大 number 的點

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Init
    for i in range(n):
        dist[i][i] = 0
    for i, j, w in edges:
        dist[i][j] = dist[j][i] = w
    
    # Find the shortest distance.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    # Find the smallest count.
    min_count = float('inf')
    for i in range(n):
        count = sum(dist[i][j] <= distanceThreshold for j in range(n))
        if count <= min_count:
            min_count = count
            r = i
    
    return r

• 要注意一下 dist[i][j] = dist[j][i] = w 蠻容易漏掉中間那個 dist[j][i]