首页 > Web开发 > 详细

Leetcode-743 Network Delay Time(网络延迟时间)

时间:2019-03-20 19:45:24      阅读:238      评论:0      收藏:0      [点我收藏+]
 1 #define INF 0x3f3f3f3f
 2 const int maxn = 503;
 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 4 struct edge
 5 {
 6     int to;
 7     int cost;
 8 };
 9 
10 //G[s].push_back(t);from s to t,directed
11 
12 class Solution
13 {
14     public:
15         int d[maxn];
16         int V,E;
17         vector<edge> G[maxn];
18     //from s to other V
19         void shortest_path(int s)
20         {
21             _for(i,0,V)
22             d[i] = INF;
23 
24             d[s] = 0;
25             while(1)
26             {
27                 bool update = false;
28                 _for(i,0,V)
29                 {
30                     _for(j,0,G[i].size())
31                     {
32                         edge e = G[i][j];
33                         if(d[i] != INF && d[e.to] > d[i] + e.cost)
34                         {
35                             d[e.to] = d[i] + e.cost;
36                             update = true;
37                         }
38                     }
39                 }
40                 if(!update) break;
41             }
42         }
43         int networkDelayTime(vector<vector<int>>& times, int N, int K)
44         {
45             V = N;
46             _for(i,0,times.size())
47             {
48                 G[times[i][0]-1].push_back(edge{times[i][1]-1,times[i][2]});
49                 E ++;
50             }
51             
52             shortest_path(K-1);
53           //  cout << d[1] << endl;
54             int cnt = 0;
55             _for(i,0,V)
56             {
57                 if(d[i]==INF)   return -1;
58                 cnt = max(cnt,d[i]);
59             }
60             return cnt;
61         }
62 };

 

Leetcode-743 Network Delay Time(网络延迟时间)

原文:https://www.cnblogs.com/Asurudo/p/10567037.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!