关于lhx大佬对dijkstra的一个优化

· · 个人记录

问题描述：

可以看一下这份60分代码，它TLE了，而且使用了堆优化，常数大小也能接受。

解决方案描述

可以发现，在一个图中，初始时全都是无穷大，不是最优解，所以肯定先有一轮更新。在之后的更新中，如果发现当前目标点已经是最优值，那么不用将目标点加入队列继续更新，因为如果是最优值那么肯定更新过，并且之前更新时肯定从目标点出发过。

根据图来


根据dij的步骤：
1、更新 1 \rightarrow 2 \rightarrow 5这条路径。此时 dis[2]=1，dis[5]=100。
2、更新 1 \rightarrow 2 \rightarrow 4 \rightarrow 5这条路径。此时 dis[2]=1，dis[4]=2，dis[5]=3。
3、更新 1 \rightarrow 3 \rightarrow 4 ，此时发现4已经是最优解了，略过（可以发现这是因为之前已经更新的时候经过了 4，所以是最优解，同时可以发现之前更新的过程中从4 出发过，所以从 4 出发的路径也都得到了更新，所以不用重新将4加入队列了）
后面的步骤省略

代码实现：

将： 

if(dis[to]>dis[u]+edge[i].w){
    dis[to] = dis[u] + edge[i].w;
}
que.push(make_pair(-dis[to], to));

改为：

if(dis[to]>dis[u]+edge[i].w){
    dis[to] = dis[u] + edge[i].w;
   que.push(make_pair(-dis[to], to));
}

优化正确性解释：

见第三步解释

效果：

修改后的代码AC了