我看之前好多人在讨论区里问了。我发现很多 Dijkstra 题解是 $O(NM)$ 的。不过这题数据范围太小了卡不了 TLE。

卡成 $O(NM)$ 的构造思路是这样的：

实际构造就是把 $1$ 到 $5$ 的链造的尽可能长（可以到 $O(N)$ 级别）。$5$ 号点的次短路会被更新 $N$ 次，也就说 $5$ 号点会入堆 $N$ 次。这个点每次出堆的时候，它要把它所有出边都走一遍，然而出边可以有 $O(M)$ 条。这样就是 $O(NM)$ 了。

我造了一个 $N=20000$ 的数据，题解里很多代码已经跑的很慢了，下面是 gen。

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("1.in","w",stdout);
	
	cout << 20000 << ' ' << 100000 << '\n';
	for(int i = 1;i <= 9999;i ++) cout << i << ' ' << i + 1 << ' ' << 1 << '\n';
	for(int i = 1;i <= 9999;i ++) cout << i << ' ' << i + 10000 << ' ' << 1 << '\n';
	for(int i = 10001;i <= 19999;i ++) cout << i << ' ' << 10000 << ' ' << 20000 - 2 * (i - 10001) << '\n';
	for(int i = 9999 + 9999 + 9999 + 1;i <= 100000;i ++) cout << 10000 << ' ' << 20000 << ' ' << i - (9999 + 9999 + 9999) << '\n';
	
//	cout << 5000 << ' ' << 100000 << '\n';
//	for(int i = 1;i <= 2499;i ++) cout << i << ' ' << i + 1 << ' ' << 1 << '\n';
//	for(int i = 1;i <= 2499;i ++) cout << i << ' ' << i + 2500 << ' ' << 1 << '\n';
//	for(int i = 2501;i <= 4999;i ++) cout << i << ' ' << 2500 << ' ' << 5000 - 2 * (i - 2501) << '\n';
//	for(int i = 2499 + 2499 + 2499 + 1;i <= 100000;i ++) cout << 2500 << ' ' << 5000 << ' ' << i - (2499 + 2499 + 2499) << '\n'; 失败的尝试
	return 0;
}

但 Dijkstra 可以做到 $O(n\log n)$ 的，实际上只要限制更新次数就行了。这里的问题就在于 $5$ 号点出堆更新了太多次，但后面的出堆更新其实是没有意义的，因为第 $3$ 次以后出堆（确切的说是第三大的数）的答案绝对不会是次短路的一部分。只有前 $2$ 次出堆更新才对后面的点的最短路/次短路答案真正有影响。所以每个点在前 $2$ 次出堆的时候用堆里取出来的 dis 更新一遍即可。（如果 dis 有重复，要跳过且不计入次数）这个做法对严格 $k$ 短路也适用。

不过其实堆不会出现重复元素，并不需要考虑重复。

这两篇应该是对的：
https://xuan00.blog.luogu.org/p2865-lu-zhang-ci-duan-lu-zhang-du-dijkstra-you-xian-dui-lie-post
https://www.luogu.com.cn/blog/Fheiwn/solution-p2865
这句话可以保证这一点。

if(dis>dis2[x]) continue;

这篇也对，但是有句话感觉写错了，第 42 行的 dis[e[i].v][0] 应该是 dis[e[i].v][1] 但我也叉不掉：
https://www.luogu.com.cn/blog/Glacier-elk/roadblocks

这个题还有另一种做法，这个做法也是 $O(N\log N)$ 的，把题解里 SPFA 改成 Dij 就行了：https://www.luogu.com.cn/blog/233xsbl233/solution-p2865

没写 Dijkstra 的题解我就没看了。然后这题数据真的强度不行，可以考虑来个加强版（？）