Fork me on GitHub

Network Delay Time

Posted on

Description

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<int>> graph(N + 1, vector<int>(N + 1, 100000));
        for (auto& time : times)
            graph[time[0]][time[1]] = time[2];
        
        vector<bool> visited(N+1, false);
        visited[K] = true;
        int ret = -100000;
        int count = 0;
        while(count < N - 1) {
            int minLens = 100000;
            int minIndex = -1;
            for (int i = 1; i <= N; ++i) {
                if (visited[i]) continue;
                if (graph[K][i] < minLens) {
                    minLens = graph[K][i];
                    minIndex = i;
                }
            }
            if (minLens == 100000) return -1;
            visited[minIndex] = true;
            ret = max(ret, minLens);
            //update
            for (int i = 1; i < graph[K].size(); ++i) {
                if (visited[i]) continue;
                int minium = min(graph[K][i], minLens + graph[minIndex][i]);
                graph[K][i] = minium;
            }
            ++count;
        }
        
        return ret;
    }
};