743. 网络延迟时间
题目
有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
解题思路
最短路径，DisjKstra算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190class Solution {
private int v;
boolean[] inqueue;
private LinkedList<Edge> adj[];
PriorityQueue[] queue;
private class Vertex{
private int id;
private int dist;
public Vertex(int id ,int dist){
this.id = id;
this.dist =dist;
}
}
private class Edge{
private int src;
private int dst;
private int dist;
public Edge(int src ,int dst ,int dist){
this.src =src;
this.dst = dst;
this.dist = dist;
}
}
class PriorityQueue{
private Vertex[] nodes;
private int count;
private int n;
public PriorityQueue(int v){
this.nodes = new Vertex[v+1];
this.count =0;
this.n = v;
}
public void add(Vertex ver) {
if(count>=n){return;}
nodes[++count]=ver;
int i=count;
while(i/2>0&&nodes[i/2].dist>nodes[i].dist) {
Vertex temp=nodes[i/2];
nodes[i/2]=nodes[i];
nodes[i]=temp;
i=i/2;
}
}
public Vertex poll() {
if(count<1){return null;}
Vertex temp=nodes[1];
nodes[1]=nodes[count];
nodes[count] = null;
count--;
heaplify(nodes,count,1);
return temp;
}
private void heaplify(Vertex[] a,int n,int i) {
if(n<1){return;}
int min=i;
while(true) {
//找到子节点比该结点小的中较小的
if(2*i<=n&&a[2*i].dist<a[min].dist) {
min = 2 * i;
}
if(2*i+1<=n&&a[2*i+1].dist<a[min].dist){min=2*i+1;}
//该节点比子节点大堆化完毕
if(min==i){ return;}
//交换两节点
Vertex temp=a[min];
a[min]=a[i];
a[i]=temp;
i=min;//迭代条件
}
}
public void update(Vertex vertex) {
int i=1;
boolean exist = false;
for(;i<=n;i++) {
if(nodes[i]!= null && nodes[i].id==vertex.id){
exist = true;
break;
}
}
if(!exist){
add(vertex);
}else{
nodes[i].dist=vertex.dist;
}
heaplify(nodes,count,i);
}
public boolean isEmpty() {
if(count<1)return true;
return false;
}
private void treeifyUp(int k){
if(k > count +1){
return;
}
int i = k;
while(i < 1){
i = k/2;
if(nodes[i].dist > nodes[k].dist){
Vertex temp = nodes[i];
nodes[i] = nodes[k];
nodes[k] = temp;
}else{
break;
}
}
}
private void treeifyDown(int k){
int i = k;
while(i < count/2){
int left = i*2;
int right = i*2+1;
if(nodes[left].dist < nodes[i].dist){
Vertex tmp = nodes[i];
nodes[i] = nodes[left];
nodes[left] = tmp;
i = left;
}else if(nodes[right].dist < nodes[i].dist){
Vertex tmp = nodes[i];
nodes[i] = nodes[right];
nodes[right] = tmp;
i = right;
}else{
break;
}
}
}
}
public int networkDelayTime(int[][] times, int N, int K) {
this.v = N;
Vertex[] vertexs = new Vertex[v+1];
this.inqueue = new boolean[v+1];
this.queue = new PriorityQueue[v];
int first = times.length;
int second = times[0].length;
adj = new LinkedList[N+1];
for(int l= 0 ; l < N+1 ; l++){
adj[l] = new LinkedList<Edge>();
if(l != 0){
vertexs[l] = new Vertex(l,Integer.MAX_VALUE);
}
}
for(int m = 0 ; m< first ; m++){
int src = times[m][0];
adj[src].add(new Edge(times[m][0],times[m][1],times[m][2]));
}
PriorityQueue queue = new PriorityQueue(this.v);
vertexs[K].dist = 0;
queue.add(vertexs[K]);
inqueue[K] = true;
while(!queue.isEmpty()){
Vertex minVertex = queue.poll();
int minVertexId = minVertex.id;
LinkedList<Edge> list = adj[minVertexId];
for(int i = 0 ; i< list.size() ; i++){
Edge edge = list.get(i);
Vertex nextVertex = vertexs[edge.dst];
if(nextVertex.dist > edge.dist + minVertex.dist){
nextVertex.dist = edge.dist + minVertex.dist;
if(inqueue[nextVertex.id]){
queue.update(nextVertex);
}else{
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
}
}
}
int d = 0;
for(int q = 1 ; q <= N ; q++){
if(vertexs[q].dist == Integer.MAX_VALUE){
return -1;
}
if(d < vertexs[q].dist){
d = vertexs[q].dist;
}
}
return d;
}
}
好不容易通过测试，找到临接表，从顶点开始，依次便利顶点相连的所有节点，将每个节点的vertex放入最小堆里面，然后弹出最小的值的节点，继续重复上面的循环，知道最小堆为空。有一个数组保存已经访问过的数据，保证不重复访问。如果堆里有，就更新数据，重新对花堆化。
我不能说完全明白，但经过一个星期的思考，从完全懵逼到入门了。还需要继续深入理解。
