Solution using Floyd-Warshall All-Pairs Shortest Path O(N^3)


  • 0
    D

    It's easier (but less efficient) to use the floyd-warshall algorithm to get all pairs shortest path, and then pick the ones which start at node K.

    class Solution {
    public:
        int networkDelayTime(vector<vector<int>>& times, int N, int K) {
            const int INF = 110 * 6000;
            vector<vector<int>> dp(N + 1, vector<int>(N + 1, INF));
            
            for (auto t: times) {
                dp[t[0]][t[1]] = t[2];
            }
            for (int i = 1; i <= N; ++i) {
                dp[i][i] = 0;
            }
            
            for (int k = 1; k <= N; ++k) {
                for (int i = 1; i <= N; ++i) {
                    for (int j = 1; j <= N; ++j) {
                        if (dp[i][k] + dp[k][j] < dp[i][j]) {
                            dp[i][j] = dp[i][k] + dp[k][j];
                        }
                    }
                }
            }
            
            int maxTime = -1;
            for (int v = 1; v <= N; ++v) {
                if (dp[K][v] == INF) return -1;
                maxTime = std::max(maxTime, dp[K][v]);
            }
            return maxTime;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.