Floyd-Warshall解題テンプレート、ACの高速化を支援

Floyd-Warshallは任意の2点間の最短経路を解決するアルゴリズムで、LeetCodeには多くの問題が使われています.この解題テンプレートをマスターしてACを高速にすることができます.
タイトルアドレス(1334.しきい値距離内の隣人が最も少ない都市)
https://leetcode-cn.com/probl...
タイトルの説明

  n    ，   0   n-1   。        edges，   edges[i] = [fromi, toi, weighti]    fromi   toi             ，          distanceThreshold。

                   、           distanceThreshold    。          ，          。

  ，     i   j                      。

 

   1：

  ：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
  ：3
  ：       。
         distanceThreshold = 4          ：
   0 -> [   1,    2] 
   1 -> [   0,    2,    3] 
   2 -> [   0,    1,    3] 
   3 -> [   1,    2] 
   0   3       4      2      ，           3，        。
   2：

  ：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
  ：0
  ：       。 
         distanceThreshold = 2          ：
   0 -> [   1] 
   1 -> [   0,    4] 
   2 -> [   3,    4] 
   3 -> [   2,    4]
   4 -> [   1,    2,    3] 
   0       4      1      。
 

  ：

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
   (fromi, toi)      。

構想
この問題の本質は次のとおりです.

無方向図の中で各2つの町の最小距離を探し、Floyd-Warshallアルゴリズム(英語:Floyd-Warshall algorithm)を使用し、中国語ではフロイドアルゴリズムとも呼ばれ、任意の2点間の最短経路を解決するアルゴリズムである.

最小距離がdistanceThreshold以下の町をスクリーニングする.

各都市を統計して、その条件を満たす都市は何個の

があります

最小限のものを見つければ

です
Floyd‐Warshallアルゴリズムの時間的複雑さと空間的複雑さは共に$O(N^3)$であり,空間的複雑さは$O(N^2)$に最適化できる.Floyd-Warshallの基本思想は,各2点間の最小距離について,中間ノードkを通過するか,通過しないかのどちらかであり,両者の最小値をとる動的計画思想であり,詳細な解法はFloyd-Warshallアルゴリズム(wikipedia)を参照できる.
コード#コード#
コードサポート:Python 3
Python3 Code:

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        #   dist  
        dist = [[float('inf')] * n for _ in  range(n)]
        for i, j, w in edges:
            dist[i][j] = w
            dist[j][i] = w
        for i in range(n):
            dist[i][i] = 0
        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])

        #   
        res = 0
        minCnt = float('inf')
        for i in range(n):
            cnt = 0
            for d in dist[i]:
                if d <= distanceThreshold:
                    cnt += 1
            if cnt <= minCnt:
                minCnt = cnt
                res = i
        return res

キー解析

Floyd-Warshallアルゴリズム

本明細書で与えられたFloyd-Warshallアルゴリズムを解題テンプレートとして

を使用することができます.