先簡單回顧一下，今天預計分析的題目：

題目連結：https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

題目敘述

• 有 n 個城市，編號從 0 ~ n-1，題目會給一些邊，從 i 點到 j 點的權重
• distanceThreshold 類似遊戲中的精力值，最多只能走 distanceThreshold 權重的路
• 題目要找出一個城市，它到達其他城市數目最少
  • 若有多個到達數量一樣少的城市，則回傳編號最大的
    

測資的 Input/Output

• 有 n 個城市
• edges 為城市到城市間的路徑權重
• distanceThreshold 類似精力值，你走的路徑權重和不得大於 distanceThreshold
• 回傳能夠抵達最少數量的城市，若有多個這樣的情況，則回傳編號最大的城市
  • 以範例1為例，city 0 與 city 3 都只能抵達兩個城市，則回傳編號較大的 city 3
    

首先利用 Floyd-Warshall 計算任兩城市間的最短路徑長。此處建立 distance 陣列用以紀錄 DP 狀態

• 初始狀態：
  • 不經過任何中繼站時，任兩點的距離。
  • 若無法到達目的地，則距離為無限大。

# Initialize
distance = [ [ float('inf') ] * n for i in range(n) ]
for i in range(n): distance[i][i] = 0
for i in edges: 
    distance[i[0]][i[1]] = i[2] 
    distance[i[1]][i[0]] = i[2] 

• 開始計算 Floyd-Warshall，不斷更新 distance

# Floyd-Warshall
for i in range(n):
    for j in range(n):
        for k in range(n):
            distance[j][k] = min(distance[j][i] + distance[i][k], distance[j][k])

• 最後統計每個城市可以抵達的其他城市，找出數量最少者

# Count Neighbor
countNeighbor = [len(list(filter(lambda x: x <= distanceThreshold, distance[i]))) - 1 for i in range(n)]
return min(range(n), key=lambda x: (countNeighbor[x], -x))

• 完整程式碼如下：

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # Initialize
				distance = [ [ float('inf') ] * n for i in range(n) ]
        for i in range(n): distance[i][i] = 0
        for i in edges: 
            distance[i[0]][i[1]] = i[2] 
            distance[i[1]][i[0]] = i[2] 

        # Floyd-Warshall
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    distance[j][k] = min(distance[j][i] + distance[i][k], distance[j][k])

				# Count Neighbor
        countNeighbor = [len(list(filter(lambda x: x <= distanceThreshold, distance[i]))) - 1 for i in range(n)]
        return min(range(n), key=lambda x: (countNeighbor[x], -x))