C++刷leetcode（743. 网络延迟时间）【迪杰斯特拉算法】【广度优先搜索】
题目描述：有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
示例：
输入：times = [,,], N = 4, K = 2
输出：2
注意:
N 的范围在 之间。
K 的范围在 之间。
times 的长度在 之间。
所有的边 times = (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].push_back(make_pair(times, times));
}
//迪杰斯特拉
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.size();
for(int i = 0; i < len; i++){
int distance = graph.second + temp1.first;
temp.push(make_pair(distance, graph.first));
}
}
}
}
if(store.size() != N) return -1;
int res = 0;
for(int i = 0 ; i < store.size(); i++){
res = max(res, store.first);
}
return res;
}
};
参考视频：https://www.bilibili.com/video/BV1ts41157Sy?from=search&seid=1846723167994832380 终于写出来了，想了好久{:10_284:}
页:
[1]