有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
1 class Solution { 2 public: 3 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 4 vector<vector<int>>G(N,vector<int>(N,1000)); 5 vector<int>dist(N,1000); 6 for(int i = 0;i<times.size();i++){ 7 G[times[i][0]-1][times[i][1]-1] = times[i][2]; 8 } 9 ////////////////////////////////////////////////////////////// 10 for(int i = 0;i<N;i++){ 11 dist[i] = G[K-1][i]; 12 } 13 ////////////////////////////////////////////////////////////// 14 vector<int>s(N,0); 15 s[K - 1] = 1; 16 dist[K - 1] = 0; 17 int num = 1; 18 int max = 0; 19 while(num < N){ 20 int min = 1000; 21 int next = -1; 22 for(int i = 0;i<N;i++){ 23 if(s[i] == 0&&dist[i] < min){ 24 min = dist[i]; 25 next = i; 26 } 27 } 28 if(min == 1000) 29 return -1; 30 s[next] = 1; 31 num++; 32 for(int i = 0;i<N;i++){ 33 if(dist[i] > dist[next]+G[next][i]&&G[next][i] != 1000){ 34 dist[i] = dist[next] +G[next][i]; 35 } 36 } 37 } 38 for(int i = 0;i < N;i++){ 39 if(max < dist[i]) 40 max = dist[i]; 41 } 42 return max; 43 } 44 };