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

糖逗

题目描述：

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

 

示例：



输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2
 

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        //建立图
        map<int, vector<pair<int, int> > > graph;
        for(int i = 0; i < times.size(); i++){
            graph[times[i][0]].push_back(make_pair(times[i][1], times[i][2]));
        }
        //迪杰斯特拉
        vector<pair<int, int> > store;
        priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > >temp;
        temp.push(make_pair(0, K));
        vector<int> store1;
        while(!temp.empty()){
            pair<int, int> temp1 = temp.top();
            temp.pop();
            if(store.empty() || std::find(store1.begin(), store1.end(), temp1.second) == store1.end()){
                store.push_back(temp1);
                store1.push_back(temp1.second);
                if(graph.find(temp1.second) != graph.end()){
                    int len = graph[temp1.second].size();
                    for(int i = 0; i < len; i++){
                        int distance = graph[temp1.second][i].second + temp1.first;
                        temp.push(make_pair(distance, graph[temp1.second][i].first));
                    }
                }
            }
        }
        if(store.size() != N) return -1;
        int res = 0;
        for(int i = 0 ; i < store.size(); i++){
            res = max(res, store[i].first);
        }
        return res;
    }
};

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

糖逗

终于写出来了，想了好久