自动搬运

查看原文

来自洛谷，原作者为

	hxhhxh 

搬运于2025-08-24 23:10:28，当前版本为作者最后更新于2025-04-16 14:49:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

尝试刻画这个错误的 floyd 能得到哪些路径，发现其实没有那么复杂，还是刻画得出来的。

下面约定 $i\sim j$ 表示 $i$ 到 $j$ 的一条有向路径，$i\to j$ 表示 $i$ 到 $j$ 的一条有向边。

假设现在最外层枚举到 $(s,t)$（这里假设 $s<t$，不满足可以建反图再跑一遍），那么下面这些 $s\sim t$ 的路径会被考虑：

1. $s\to t$；
2. $s\to p\to t$；
3. $s\sim p\to t$，其中 $s<p<t$，且 $s\sim p$ 的路径会被考虑；
4. $s\sim p\sim t$，其中 $p<s$，且 $s\sim p$ 和 $p\sim t$ 的路径会被考虑。

注意这是一个递归的结论。可以归纳出，所有 $s\sim t$（假设 $s<t$）的被考虑的路径为以下形式：

其中，$k$ 可以等于 $l$，且有以下性质：

1. $p_l=t$，$p_k>s$；
2. $\forall i\in[k,l),p_i<p_{i+1}$；
3. $\nexists i\in[2,k),\min(p_i,p_{i-1})>s$。

也就是说，所有被考虑的从 $s$ 到 $t$ 的路径都是从 $s$ 开始在原图上走，但是不能连续两步都在 $\geq s$ 的点上；然后在第一次违反这个限制后只能向编号更大的点走，最终走到 $t$。

这是一个非常好的结论，以至于我们可以直接利用它来求出错误的最短路。

首先枚举 $s$，忽略两端都大于 $s$ 的边后跑一遍最短路，可以考虑到 $s\sim p_{k-1}$ 的所有路径；然后保留原图上的所有边，可以考虑到 $p_{k-1}\to p_k$；最后只保留从编号小的点到编号大的点的边，可以考虑到 $p_k\sim p_l$。将这三部分拼起来就可以求出错误的最短路了。

时间复杂度为 $O(n(n+m)\log n)$，空间复杂度为 $O(n^2+m)$，可以求出题面代码给出的最短路矩阵。在本题中空间也可以做到 $O(n+m)$，可以把空间限制开到 1M。

下面是代码

#include<bits/stdc++.h>
using namespace std;
const int N=2222;
int n,m,D[N],t[N],o[N],p;
vector<pair<int,int> >e[N],g[N];
void dij(vector<pair<int,int> >*E,int S,int L,int*s){
	for(int i=1;i<=n;i++) o[i]=s[i]=1e9;
	priority_queue<pair<int,int> >q;
	for(q.push({s[S]=0,S});q.size();){
		int x=q.top().second;
		q.pop();
		if(o[x]<1e9) continue;
		o[x]=s[x];
		for(auto[i,v]:E[x]) if(i<=L||x<=L) if(s[i]>v+s[x]) q.push({-(s[i]=v+s[x]),i});
	}
	for(int i=1;i<=n;i++) for(auto[j,v]:E[i]) s[j]=min(s[j],o[i]+v);
	for(int i=L+1;i<=n;i++) for(auto[j,v]:E[i]) if(j>i) s[j]=min(s[j],s[i]+v);
}
int main(){
	cin>>n>>m;
	for(int i=1,j,k,l;i<=m;i++){
		scanf("%d %d %d",&j,&k,&l);
		e[j].push_back({k,l});
		g[k].push_back({j,l});
	}
	for(int i=1;i<=n;i++){
		dij(e,i,n,D);
		dij(e,i,i,t);
		for(int j=i+1;j<=n;j++) p+=t[j]!=D[j];
	}
	for(int i=1;i<=n;i++){
		dij(g,i,n,D);
		dij(g,i,i,t);
		for(int j=i+1;j<=n;j++) p+=t[j]!=D[j];
	}
	cout<<p;
}