# 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.

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;}
};