【最短路】dj堆优化的细节处理

先不多说，记录一下对如下代码的理解：

while(!pq.empty()) {
	int now = pq.top().first;
	pq.pop();
	if(visited[now] == 1) {
		continue;
	}
	visited[now] = 1;
	for(pair<int,int> e : nodes[now]->edge) {
		int enode = e.first;
		int eval = e.second;

		if(visited[enode] == 1) {
			continue;
		}
		if(eval + minDist[now] < minDist[enode]) {
			minDist[enode] = eval + minDist[now];
			path[enode] = now;
			pq.push({enode,minDist[enode]});
		}
	}
}

难点在于：

• 为什么循环终止条件是pq为空？

• pq存了重复的点怎么办？

• pq什么时候push，push什么进去？

先说第三个问题。由于pq用于辅助找出minDist中的最小值及其下标，用于找到当前离源点最近的点。于是除了第一次需要加入源点外，其他情况当且仅当minDist 发生变化时才将变化后的结果存入pq。

然后是第一个和第二个问题：虽然pq会重复存点，但是堆顶永远是当前最近的点，所以不影响循环内部；并且当pq只剩重复的点时，堆顶会输出一个visited为1的点，此时不会进入后续操作，因此重复也无所谓，会直接一整套循环将pq全部弹出，然后结束循环，这就是循环终止条件的由来