题解：P11819 [PA 2019 Final] Floyd-Warshall

· · 题解

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

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

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

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

s\to p_1\to p_2\to\dots\to p_k\to\dots\to p_l

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

也就是说，所有被考虑的从 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;
}