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

題目
思路:

  • 要找的點是可到達的點的距離在 threshold 裡的那些點,所以要找的是最短距離,因為只要最短距離可以在 threshold 內,那它就是可到達的點
  • 用 Floyd-Warshall’s algorithm 找到所有點之間的最小距離
    • kij 之間的任意點。比較 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.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×