题解：P14184 有向无权图删边最短路

· · 题解

upd on 2025/10/17：修改了错误内容，现在时间复杂度是正确的，可以不管评论区提到的错误了。

如有不对请再次提出，我会虚心改正的。

本文摘抄自 EI's blog，稍微进行了一些补充。

我们先求出一条 s 到 t 的某条最短路。然后不在这条最短路上的边删去不影响最短路，直接得出结果。

于是我们只需要考察这条路径上每条边被删除的时候的最短路。

对比原来的最短路，容易发现删边后 只需要离开原来的最短路一次。

具体的：记原来的最短路为 p_1=1,p_2,\dots,p_k=n，那么新的最短路在 p_i 处离开，在 p_j 处重新回来，且 i<j。

考虑设置阈值 B，当 p_i 到 p_j 的这条外部路径的长度超过或不超过 B 的时候，我们分别处理。

短

注意到从 p_i 到 p_j 的一条外部路径长度一定不小于 j-i。

我们可以一次性处理所有 i \bmod (B+1) 为同一个值作为起点的 i。因为 i-B-1<i\le j 时候，i-B-1 的贡献一定 >B，在此时就没有影响。

从它们开始做多源 BFS，可以在 \mathcal{O}(m) 的时间内得到到每个点的对应的外部路径长度。

具体怎么做呢？

称路径上 \bmod\ B+1=r 的点为当前的关键点。

多源 BFS 时候起点要有初始权值 dis_u，就是原来的最短路。

然后考虑按顺序加入关键点，假设加入到 u。并且 BFS 的时候强制要求路径长度不能超过 dis_u+B，这样就不会有多余的影响。

最后再做一个类似后缀 \min 的东西，具体请参考代码理解。

这部分复杂度为 \mathcal{O}(mB)。

长

随机选一个点，考虑用经过它的外部路径来更新答案。

只需要在正图和反图上做 BFS 以及做前缀、后缀的 \min 就能在 \mathcal{O}(m) 时间内更新。

由于我们考虑的都是 \ge B 的路径，所以每条路径有 \ge \frac{B}{n} 的概率命中。

随机 \frac{n}{B} 次，就只有 \left(1 - \frac{B}{n}\right)^{\frac{n}{B}} \le \frac{1}{e} 的概率失败。

因此，总共随机 k\ln n \cdot \frac{n}{B} 次，根据 union bound 就保证了有 \ge 1 - n^{1- k} 的概率成功计算出所有答案。

这部分复杂度为 \mathcal{O}\left(m\log n\cdot \frac{n}{B} \right)。

清算

综上，取 B=\sqrt {n\log n}，我们在 \mathcal{O}\left(m\sqrt{n\log n}\right) 的时间内解决。

根据两边常数，实际取 B=4000 较好。k 在 n 比较大时直接取 2 就行。

:::info[代码]

// 洛谷 P14184
// https://www.luogu.com.cn/problem/P14184
#include<bits/stdc++.h>
#define LL long long
#define bs basic_string<int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1e5+5,B=4000,inf=0x3f3f3f3f;
int n,m,d[N],u[N],pre[N],ans[N],t,a[N],b[N],p[N];bool in[N],v[N];
struct node{int u,v;}e[N];
vector<pair<int,int>>E[N];bs G[N],_G[N];
inline void cmn(int &x,int y){x=min(x,y);}
inline void gd()
{
    fill_n(d+1,n,-1);d[1]=0;
    queue<int>q;q.push(1);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(auto [y,w]:E[x]) if(d[y]==-1)
            d[y]=d[x]+1,pre[y]=w,q.push(y);
    }
    if(d[n]==-1){while(m--) puts("-1");exit(0);}
    for(int i=n;i!=1;)
    {
        in[pre[i]]=1;b[++t]=pre[i];
        auto [u,v]=e[pre[i]];i^=u^v;a[t]=i;
    }
    reverse(a+1,a+1+t);reverse(b+1,b+1+t);a[++t]=n;
    for(int i=1;i<=m;i++) if(!in[i])
    {
        auto [u,v]=e[i];
        ans[i]=d[n];G[u]+=v,_G[v]+=u;
    }memset(in,0,sizeof(in));
    for(int i=1;i<=t;i++) in[a[i]]=1;
}
int q[N],hd,tl;
inline void bfs(int x,auto G,int *d)
{
    fill_n(d+1,n,-1);hd=1,tl=0;
    d[x]=0,q[++tl]=x;
    while(hd<=tl)
    {
        int x=q[hd++];
        for(int y:G[x]) if(d[y]==-1)
            d[y]=d[x]+1,q[++tl]=y;
    }
}
inline void sm()
{
    int L=min(B,n);
    for(int o=0;o<=min(L,t);o++)
    {
        hd=1,tl=0;
        for(int i=1;i<=n;i++) v[i]=0,d[i]=inf;
        int nw=-1e9,T=1;
        while(hd<=tl||T<=t)
        {
            if(hd>tl||d[q[hd]]>nw)
            {
                while(T<=t&&(T-1)%(L+1)!=o) v[a[T++]]=1;
                if(T<=t)
                {
                    d[a[T]]=T-1;int x=a[T++];
                    nw=d[x]+L;q[++tl]=x;v[x]=1;
                }
            }
            if(hd>tl) continue;int x=q[hd++];
            if(d[x]>nw) continue;//nw 做限制
            for(int y:G[x]) if(!v[y]) d[y]=d[x]+1,v[y]=1,q[++tl]=y;
        }
        for(int i=t;i;i--) if((i-1)%(L+1)!=o)
        {
            int u=a[i],v=(i<t)?a[i+1]:0;
            if(i%(L+1)!=o&&v) d[u]=min(d[u],d[v]-1);
            cmn(ans[b[i-1]],d[u]+t-i);
        }//后缀 min 贡献
    }
}//多源 bfs
inline void bg()
{
    int T=2*log(n)*n/B;
    iota(p,p+1+n,0);shuffle(p+1,p+1+n,rnd);
    for(int i=1,x=p[1];i<=T;x=p[++i])
    {
        bfs(x,_G,d),bfs(x,G,u);fill_n(pre,t,inf);
        for(int i=1;i<t;i++){
            pre[i]=pre[i-1];
            if(~d[a[i]]) cmn(pre[i],d[a[i]]+i-1);
        }int mn=inf;
        for(int i=t;i>1;i--)
        {
            if(~u[a[i]]) cmn(mn,u[a[i]]+t-i);
            cmn(ans[b[i-1]],mn+pre[i-1]);
        }
    }
}//大的
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[i]={u,v},E[u].push_back({v,i});
    memset(ans,inf,sizeof(ans));gd();sm();bg();
    for(int i=1;i<=m;i++) cout<<(ans[i]>=n?-1:ans[i])<<"\n";
    return 0;
}

:::