Leetcode算法学习日志-743 Network Delay Time

2018-01-24 10:31:14来源:网络收集作者:程序诗人人点击

分享

[var1]Leetcode 743 Network Delay Time
题目原文

There are N network nodes, labelled
1 to N.


Given times, a list of travel times as
directed edges times[i] = (u, v, w), where u is the source node,
v is the target node, and w is the time it takes for a signal to travel from source to target.


Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return
-1.


Note:


N will be in the range [1, 100].K will be in the range [1, N].The length of times will be in the range
[1, 6000].All edges times[i] = (u, v, w) will have
1 <= u, v <= N and 1 <= w <= 100.
题意分析

知道各点间的连接情况以及他们之间的延迟,问信号从某一点出发,到达所有点的时间。如果不能到大所有点,则输出-1.


解法分析

要达到所有点,则所用最长时间就是最短路径最长的点的用时。此题为带权重的单源最短路径问题,可用Dijkstra算法。Dijkstra算法结合了广度优先搜索和prim算法,它维护了一个集合S,代表已经确定最短路径的点,V代表所有节点,每次算法从V-S中选择路径长度最短的节点q加入S中,这是一种贪心策略,再从q出发更新它相邻节点的路径长度,取小值,直到所有点都加入S中为止。算法关键是采用一个priority_queue,用来选取V-S中路径长度最小的元素加入S,因此将V-S的元素放入优先队列中,由于本问题需要更新优先队列中元素的优先级,然而priority_queue没有提供迭代器借口,不能访问其中元素,因此需要在外面记录每个元素最新的关键字大小,通过priority_queue.push(),将优先级更高的元素放入,原元素则排在后面,不影响算法,注意这里类似广度优先搜索,只是将可扩展节点放入了优先队列中,并没有将所有节点放入。用一个数组存储每个节点的路径长度,并不断更新,最终如果有初始位INT_MAX的元素,则说明它无法到达,返回-1,不然返回最大值,C++代码如下:


class Solution {
public:
class Node{
public:
int ID;
int len;
Node(){}//默认构造函数,用于Node t的情况,下面的是非默认的构造函数,用于带参数创建对象的情况,
//不写构造函数,系统默认有上述构造函数,如果写了下述构造函数,自己最好写一个上述构造函数,避免写Node t报错
Node(int ID,int len): ID(ID),len(len) {}
};
class myCompare{
public:
bool operator()(Node &a,Node &b){//圆括号的重载
return a.len>b.len;
}
};
int networkDelayTime(vector>& times, int N, int K) {
vector>> graph(N+1,vector>());
priority_queue,myCompare> pq;
for(auto e:times){
graph[e[0]].push_back({e[1],e[2]});
}
pq.push(Node(K,0));//don't need to push all nodes in,just like BFS
vector Length(N+1,INT_MAX);//用于判断是否需要修改节点key的大小,因为不方便从优先队列中返回相应id的key大小
Length[K]=0;
Node t=pq.top();
while(!pq.empty()){
t=pq.top();
pq.pop();
for(auto p:graph[t.ID]){
int newLen=t.len+p.second;
if(Length[p.first]>newLen){
Length[p.first]=newLen;
pq.push(Node(p.first,newLen));//需要有更小key才放入
}
}
}
int res=0;
for(int i=1;i<=N;i++){
if(Length[i]==INT_MAX)
return -1;
res=max(res,Length[i]);
}
return res;}
};


最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台