【第二十五天 - Floyd-Warshall 题目分析】

先简单回顾一下，今天预计分析的题目：

题目连结：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))