洛谷3238 [HNOI2014]道路堵塞

题意

给出一个 $N$ 点 $M$ 边的有向图，并给出最短路径。依次删掉最短路上的每条边，求删边后最短路长度。

$N\le 10^5 \ , \ M\le 2\times 10^5$ 。

题解

朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ，但这样显然会爆。

可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ，那么最短路一定是

$$1\rightarrow x\rightarrow y\rightarrow N \ , \ x\le u,y\geq v$$

那么对于一个在 $v$ 后面且在最短路上的点，就可能构成答案，把这个路径长度放入一个小根堆里，即：

$$dis(1,x)+dis(x,y)+dis(y,N)$$

所以就从最短路上每条边的起点开始跑 $\text{Spfa}$，如果遇到同样是最短路上靠后的点就将答案放入小根堆。如果堆中元素在当前起点之前就将其删除。

因为 $dis(1,x),dis(y,N)$ 都在最短路上，所以可以用正反两遍前缀和更新最短路。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;
struct Edge {
    int next,to,w;
} edge[N<<1];
pii v[N];
bool vis[N],in[N];
priority_queue <pii,vector<pii>,greater<pii> > pq;
int cnt,head[N],n,m,k,a,b,c,dis[N],eg[N<<1],pos[N],id[N],f[N],g[N];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void spfa(int cur)
{
    memset(in,0,sizeof(in));
    dis[id[cur]]=f[cur];
    queue <int> q;
    stack <int> s;
    q.emplace(id[cur]);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        in[x]=0;
        for (int i=head[x];i;i=edge[i].next)
        {
            if (i==eg[cur]) continue;
            int y=edge[i].to,w=edge[i].w;
            if (pos[y]>cur) //在最短路上
            {
                if (!vis[y]) //没被记录过就记录
                {
                    vis[y]=1;
                    s.emplace(y);
                    v[y].first=dis[x]+w+g[pos[y]];
                    v[y].second=pos[y];
                }
                else v[y].first=min(v[y].first,dis[x]+w+g[pos[y]]); //否则更新答案
            }
            else if (dis[x]+w<dis[y]) //其它点照常更新最短路
            {
                dis[y]=dis[x]+w;
                if (in[y]) continue;
                in[y]=1;
                q.emplace(y);
            }
        }
    }
    for (;!s.empty();s.pop()) pq.emplace(v[s.top()]),vis[s.top()]=0;
}

signed main()
{
    n=read(); m=read(); k=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
    }
    pos[1]=id[1]=1;
    for (int i=1;i<=k;i++)
    {
        eg[i]=read();
        pos[edge[eg[i]].to]=i+1; //终点在最短路上的位置是 i+1
        id[i+1]=edge[eg[i]].to; //最短路上第 i+1 个点的编号
    }
    for (int i=2;i<=k;i++) f[i]=f[i-1]+edge[eg[i-1]].w; //前缀和预处理最短路上距离
    for (int i=k;i>=2;i--) g[i]=g[i+1]+edge[eg[i]].w;
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=k;i++)
    {
        spfa(i);
        for (;!pq.empty() && pq.top().second<=i;pq.pop()); //如果 y 在 x 之前就淘汰
        if (pq.empty()) puts("-1");
        else printf("%d\n",pq.top().first);
    }
    return 0;
}