众所周知，dijkstra 算法有一个叫做堆优化的东西，不难写出下面这份代码：

memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
q.emplace(0, s);
while (q.size()) {
	int u = q.top().second;
	q.pop();
	if (cfg[u]) continue;
	else cfg[u] = 1;
	for (auto [v, w] : G[u])
		if (dis[v] > dis[u] + w) {
			dis[v] = dis[u] + w;
			q.emplace(-dis[v], v);
		}
}

这份代码的时间复杂度网上广为流传的是 $O((n+m)\log n)$，不过事实上可能应该也许大概是 $O((n+m)\log m)$。

卡满的构造方法也不难想，就是先搞个菊花图，其中一条的边 $(s, v)$ 为 $1$，其它边权为 $1\,145\,141\,919\,810$，对于 $v$ 同理，一条为 $1$，其它为 $1\,145\,141\,919\,800$，这样可以保证每一次走一条出边后，新的点都会扔到堆里。

但我在前天翻 tourist 的代码时，突然发现一种 set 写法。

set<pair<int, int>> q;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
q.emplace(0, s);
while (q.size()) {
	int u = q.begin()->second;
	q.erase(q.begin());
	if (cfg[u]) continue;
	else cfg[u] = 1;
	for (auto [v, w] : G[u])
		if (dis[v] > dis[u] + w) {
			q.erase({ dis[v], v });	// 主要的区别在这
			dis[v] = dis[u] + w;
			q.emplace(dis[v], v);
		}
}

不难发现对于这份代码，每个点在 set 种只会保留一个值，所以是严格 $O((n+m)\log n)$ 的。

• priority_queue 写法：无 O2(1.35s)，有 O2(328ms)
• set 写法：无 O2(1.22s)，有 O2(395ms)

一个奇妙的现象是在不开 O2 的情况下，set 写法跑得比 priority_queue 快，而在开 O2 的情况下反之。

怎么会是呢？原因可能有以下几个：

1. 洛谷数据中没卡 priority_queue 写法。（但卡了也没有意义）
2. set 和 priority_queue 操作速度有差异。或者 O2 对 priority_queue 比较友好。
3. 评测寄波动。

本着闲的蛋疼严谨求知的精神，我们跑 30 组数据，分别取平均值后比较。

插电笔记本，CPU 是 AMD Ryzen 5 5600H。

编译命令 g++ (-O2) -std=c++20 -Wall -Wl,--stack=2610612736 -Wextra

从上表可以看出，set 带来的优越性（指 $\log n$ 和 $\log m$ 差的 $\frac{1}{2}$ 的系数）远没有其本身操作自带的大常数优秀，瑜不掩瑕。只有在特殊图且不开 O2 的情况下能和 priority_queue 比肩。

所以 set 写法不是好文明，建议还是通通写 priority_queue。

Q：那这篇讨论到底有什么意义？到底想表达什么？

A：没有意义，闲的蛋疼，现在你浪费了人生中宝贵的两分钟。

测试用到的所有源代码可以在这里找到。