C++刷leetcode（743. 网络延迟时间）【迪杰斯特拉算法】【广度优先搜索】

糖逗

题目描述：

1. 有 N 个网络节点，标记为 1 到 N。
   
2. 
   
3. 给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
   
4. 
   
5. 现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
   
6. 
   
7.  
   
8. 
   
9. 示例：
   
10. 
    
11. 
    
12. 
    
13. 输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
    
14. 输出：2
    
15.  
    
16. 
    
17. 注意:
    
18. 
    
19. N 的范围在 [1, 100] 之间。
    
20. K 的范围在 [1, N] 之间。
    
21. times 的长度在 [1, 6000] 之间。
    
22. 所有的边&#160;times[i] = (u, v, w)&#160;都有&#160;1 <= u, v <= N&#160;且&#160;0 <= w <= 100。
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/network-delay-time
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int networkDelayTime(vector<vector<int>>& times, int N, int K) {
   
4.         //建立图
   
5.         map<int, vector<pair<int, int> > > graph;
   
6.         for(int i = 0; i < times.size(); i++){
   
7.             graph[times[i][0]].push_back(make_pair(times[i][1], times[i][2]));
   
8.         }
   
9.         //迪杰斯特拉
   
10.         vector<pair<int, int> > store;
    
11.         priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > >temp;
    
12.         temp.push(make_pair(0, K));
    
13.         vector<int> store1;
    
14.         while(!temp.empty()){
    
15.             pair<int, int> temp1 = temp.top();
    
16.             temp.pop();
    
17.             if(store.empty() || std::find(store1.begin(), store1.end(), temp1.second) == store1.end()){
    
18.                 store.push_back(temp1);
    
19.                 store1.push_back(temp1.second);
    
20.                 if(graph.find(temp1.second) != graph.end()){
    
21.                     int len = graph[temp1.second].size();
    
22.                     for(int i = 0; i < len; i++){
    
23.                         int distance = graph[temp1.second][i].second + temp1.first;
    
24.                         temp.push(make_pair(distance, graph[temp1.second][i].first));
    
25.                     }
    
26.                 }
    
27.             }
    
28.         }
    
29.         if(store.size() != N) return -1;
    
30.         int res = 0;
    
31.         for(int i = 0 ; i < store.size(); i++){
    
32.             res = max(res, store[i].first);
    
33.         }
    
34.         return res;
    
35.     }
    
36. };

复制代码

参考视频：https://www.bilibili.com/video/B ... 1846723167994832380

糖逗

终于写出来了，想了好久