1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j]
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
  def shortestPath(self, n, edges, maxD) -> int:
    graph = [[sys.maxsize]*n for _ in range(n)]
    for i,j,w in edges:
      graph[i][j] = w
    for i in range(n):
      graph[i][i] = 0

    for k in range(n):
      for i in range(n):
        for j in range(n):
          graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    res = {sum(d <= maxD for d in graph[i]): for i in range(n)}

    return res[min(res)]