暴力 K 短路的一个小细节

众所周知，暴力 K 短路是这么写的：

pri.push(make_pair(0,1));
dis[1].push(0);
while(!pri.empty())
{
	u=pri.top().second;
	val=-pri.top().first;
	pri.pop();
	if(num[u]==k||dis[u].size()==k&&val>dis[u].top())continue;
	num[u]++;
	for(i=head[u];i;i=e[i].next)
	{
		v=e[i].to;
		tmp=val+e[i].w;
		if(dis[v].size()==k&&tmp<dis[v].top())dis[v].pop();
		if(dis[v].size()<k)dis[v].push(tmp),pri.push(make_pair(-tmp,v));
	}
}

如果将代码中的 num 数组去掉，是否会导致时间复杂度爆炸呢？

答案是不会的。考虑多出来的一些点，它们显然不能松弛，因为在它们之前至少有 (k) 个费用更小或相等的点进行了松弛。

所以仅仅是多枚举了一次出边而已。

可以发现，多出来的点最多只有 (k-1) 个，否则堆中最大费用也会小于多出来点的费用，就直接被 continue 掉了。

时间复杂度仍为 (O(kmlog m))。