-[1514. Path with Maximum Probability](en/1001-2000/1514-path-with-maximum-probability.md) was solved in_Python_ and 2 ways.

-[743. Network Delay Time](en/1-1000/743-network-delay-time.md) was solved in_Python_ and 2 ways.

-[787. Cheapest Flights Within K Stops](en/1-1000/787-cheapest-flights-within-k-stops.md) was solved in_Python_.

-[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](en/1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md) was solved in_Python_.

More LeetCode problems will be added soon.

LeetCode link:[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance), difficulty:**Medium**.

There are`n` cities numbered from`0` to`n-1`. Given the array edges where`edges[i] = [from_i, to_i, weight_i]` represents a bidirectional and weighted edge between cities`from_i` and`to_i`, and given the integer`distanceThreshold`.

Return the city with the smallest number of cities that are reachable through some path and whose distance is**at most**`distanceThreshold`, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities_**i**_ and_**j**_ is equal to the sum of the edges' weights along that path.

**Input**:`n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4`

**Output**:`3`

**Explanation**:

**Input**:`n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2`

**Output**:`0`

**Explanation**:

- All pairs`(from_i, to_i)` are distinct.

<details>

<summary>Hint 1</summary>

Use Floyd-Warshall's algorithm to compute any-point to any-point distances. (Or can also do Dijkstra from every node due to the weights are non-negative).

</details>

<details>

<summary>Hint 2</summary>

For each city calculate the number of reachable cities within the threshold, then search for the optimal city.

</details>

Just like the`Hints` says, you can use**Floyd-Warshall algorithm** to compute any-point to any-point shortest distances.

Or you can also do**Dijkstra algorithm** from every node due to the weights are non-negative.

* Time:`O(N^3)`.

* Space:`O(N^2)`.

classSolution:

deffindTheCity(self,n:int,edges: List[List[int]],distance_threshold:int) ->int:

dp= []

for iinrange(n):

dp.append([float('inf')]* n)

dp[i][i]=0

for i, j, weightin edges:

dp[i][j]= weight

dp[j][i]= weight

for kinrange(n):

for iinrange(n):

for jinrange(n):

dp[i][j]=min(

dp[i][j],

dp[i][k]+ dp[k][j],

)

result=-1

min_count=float('inf')

for i, rowinenumerate(dp):

count=len([distancefor distancein rowif distance<= distance_threshold])

if count<= min_count:

min_count= count

result= i

return result

* The time complexity of`Floyd–Warshall algorithm` is`V * V * V`. For a dense graph,`Floyd–Warshall algorithm` is still faster.

*`A* algorithm` use a`priority queue`,`pop()` to get the vertex closest to the destination vertex. We need to choose**proper math formula** to determine which one is the closest. We to the very near place of destination vertex, we can use some special method to make it can handle the last part.

|Algorithm name|Key implementation methods|

|Prim's algorithm||

|Kruskal's algorithm|Union-Find|

|Dijkstra's algorithm||

|Bellman-Ford algorithm||

|Algorithm name|Focus|Key implementation methods|

|Prim's algorithm|Vertices||

|Kruskal's algorithm|Edges|Union-Find|

|Dijkstra's algorithm|Vertices||

|Bellman-Ford algorithm|Edges(Vertices+Edges for SPFA)||

* Find all the prime numbers within 1000000.

- 417https://leetcode.com/problems/pacific-atlantic-water-flow/

- 222https://leetcode.cn/problems/count-complete-tree-nodes/

- 417https://leetcode.com/problems/pacific-atlantic-water-flow/

- 1584-min-cost-to-connect-all-points-2.md

- 1514-path-with-maximum-probability.md

- 1334https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance

2005-02-09 day 2

力扣链接：[1334. 阈值距离内邻居最少的城市](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance) ，难度：**中等**。

有`n` 个城市，按从`0` 到`n-1` 编号。给你一个边数组`edges`，其中`edges[i] = [fromi, toi, weighti]` 代表`from_i` 和`to_i` 两个城市之间的双向加权边，距离阈值是一个整数`distanceThreshold`。

返回在路径距离限制为`distanceThreshold` 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号**最大**的城市。

注意，连接城市_**i**_ 和_**j**_ 的路径的距离等于沿该路径的所有边的权重之和。

**输入**:`n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4`

**输出**:`3`

**解释**:

**输入**:`n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2`

**输出**:`0`

**解释**:

- 所有`(from_i, to_i)` 都是不同的。

<details>

<summary>提示 1</summary>

Use Floyd-Warshall's algorithm to compute any-point to any-point distances. (Or can also do Dijkstra from every node due to the weights are non-negative).

</details>

<details>

<summary>提示 2</summary>

For each city calculate the number of reachable cities within the threshold, then search for the optimal city.

</details>

就像`提示`据说的，你可以使用**Floyd-Warshall 算法** 计算任意两点之间的最短距离。

或者，你可以多次调用**Dijkstra 算法**，每次调用时用不同的城市做为`起始城市`。

* Time:`O(N^3)`.

* Space:`O(N^2)`.

classSolution:

deffindTheCity(self,n:int,edges: List[List[int]],distance_threshold:int) ->int:

dp= []

for iinrange(n):

dp.append([float('inf')]* n)

dp[i][i]=0

for i, j, weightin edges:

dp[i][j]= weight

dp[j][i]= weight

for kinrange(n):

for iinrange(n):

for jinrange(n):

dp[i][j]=min(

dp[i][j],

dp[i][k]+ dp[k][j],

)

result=-1

min_count=float('inf')

for i, rowinenumerate(dp):

count=len([distancefor distancein rowif distance<= distance_threshold])

if count<= min_count:

min_count= count

result= i

return result