M_sea

洛谷3238 [HNOI2014]道路堵塞
LuoguBZOJ分析乱搞 动态删边SPFA。考虑最暴力的写法怎么写,每次删掉一条边跑$\texttt{spfa}...
扫描右侧二维码阅读全文
21
2019/02

洛谷3238 [HNOI2014]道路堵塞

Luogu

BZOJ

分析

乱搞 动态删边SPFA。

考虑最暴力的写法怎么写,每次删掉一条边跑$\texttt{spfa}$就行了。

然而这样子显然会爆炸,于是要想办法优化这个删边、跑最短路的过程。

首先发现一条性质:删掉最短路上的一条边后的最短路,一定是一条形如$1\to a\to b\to n$的路径,其中$1\to a$和$b\to n$都在原最短路上。

如果我们强制让$\texttt{spfa}$不走某条边,那么当跑到了某个最短路上的点的时候,发现可以用当前的距离更新答案。

于是可以用一个堆来维护一下走到哪个点时更新了答案。这样子还可以在后面的过程中反复调用,保证全局最优。

进一步的,$dis$可以不用清空,因为在这个过程中,$dis$不会变大。

然后,每次跑$\texttt{spfa}$时要清空标记。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

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

const int N=100000+10;
const int M=200000+10;
const int inf=0x3f3f3f3f;

struct Edge { int v,w,nxt; } e[M];
int head[N],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

struct HeapNode {
    int u,d;
    bool operator <(const HeapNode& x) const {
        return d>x.d;
    }
} a[N];
priority_queue<HeapNode> heap;

int n,m,l;
int sp[N],t[N],pos[N];
int f[N],g[N],dis[N],inq[N],mark[N];
int sta[N],top=0;

inline void spfa(int s,int d,int id,int tim) {
    memset(mark,0,sizeof(mark)); inq[s]=1,dis[s]=d;
    queue<int> Q; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            if (i==id) continue; //断掉了
            int v=e[i].v,w=e[i].w;
            if (pos[v]<=tim) {
                if (dis[u]+w<dis[v]) {
                    dis[v]=dis[u]+w;
                    if (!inq[v]) Q.push(v),inq[v]=1;
                }
            } else {
                if (!mark[pos[v]])
                    mark[pos[v]]=1,sta[++top]=v,a[v].u=pos[v],a[v].d=dis[u]+w+g[pos[v]];
                else
                    a[v].d=min(a[v].d,dis[u]+w+g[pos[v]]);
            }
        }
    }
    while (top) heap.push(a[sta[top--]]);
}

int main() {
    n=read(),m=read(),l=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w);
    }
    t[1]=pos[1]=1;
    for (re int i=1;i<=l;++i)
        sp[i]=read(),t[i+1]=e[sp[i]].v,pos[t[i+1]]=i+1;
    for (re int i=1;i<=l;++i) f[i+1]=f[i]+e[sp[i]].w;
    for (re int i=l;i>=1;--i) g[i]=g[i+1]+e[sp[i]].w;
    memset(dis,0x3f,sizeof(dis));
    for (re int i=1;i<=l;++i) {
        spfa(t[i],f[i],sp[i],i);
        while (!heap.empty()) {
            int u=heap.top().u;
            if (u<=i) mark[u]=0,heap.pop();
            else break;
        }
        if (heap.empty()) puts("-1");
        else printf("%d\n",heap.top().d);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 56 PM

发表评论