743. Network Delay Time

Network Delay Time - LeetCode

1. Floyd-Warshall

from typing import *


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dp = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][i] = 0
        for time in times:
            src, dsc, cost = time
            dp[src][dsc] = cost

        for p in range(1, n + 1):
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if dp[i][j] > dp[i][p] + dp[p][j]:
                        dp[i][j] = dp[i][p] + dp[p][j]
        target_list = dp[k][1:]
        for cost in target_list:
            if cost == float("inf"):
                return -1
        return int(max(target_list))