纠正第一篇题解的错误：

本题最坏时间复杂度 $O(n^4)$。只不过 $O(n^4)$ 也恰好能通过而已。

我们注意到，在这个 Dijkstra 里面，有 $n^2$ 个状态，而每个状态都会尝试更新一遍其他状态。

所以实际上这是一个稠密图，根据经验优先队列似乎会到 $O(n^4\log n)$。 我们发现第一篇题解使用的是配对堆，但是似乎通过了我的极限数据（本地 $0.9125$ 秒）。

究其原因，是因为每个点对答案不超过 $n$，最多进行 $n^3$ 次 decrease_key 操作，所以不管配对堆的实际时间复杂度是多少，堆花的时间都不超过更新的时间。这个结论和你用优先队列还是配对堆无关，因为哪怕是优先队列，优先队列里也最多有 $n^3$ 次 pop。

因此总体时间复杂度 $O(n^4)$，希望加以更正。

最后贴一个数据生成器，使得可以让题解程序卡满 $O(n^4)$：

#include<bits/stdc++.h>
using namespace std;
int n=200,m=n/2*3-1;
int main()
{
	printf("%d %d\n",n,m);
	for(int i=3;i<=n-1;i++)
		printf("%d %d\n",i,i+1);
	for(int i=4;i<=n;i+=2)
		printf("%d %d\n",i,i-3);
	printf("1 3\n");
	printf("%d 2\n",n);
	printf("2 %d\n",n-1);
	return 0;
}