本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-11-28 15:03:58

问题描述：

可以看一下这份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了