题解 P3238 【[HNOI2014]道路堵塞】

· · 题解

出完题后快三个月然后发现自己出重题了我的题目

题意简述

给定有向正权图，多次询问删除 1 到 n 的最短路链上的一条边后 1 到 n 的最短路，不存在则输出 -1。

题目分析

首先观察到一个性质： 答案必定是任取一条非最短路径树边，从 1 出发走到其一端点，使用这条边跳到另一端点，走到 n。

Ans=\min\{Dis_{1->u}+W_{u->v}+Dis_{v->n}\}

证明：由于只删除一条树边，则只需要使用一条非树边翻越一个点；设其为点 s；则选择的非树边必然有一条边 u->v，满足 dep_u>dep_s, dep_s>dep_v。 则其他边对答案没有贡献，不如走树边，因此只需要走一条非树边；

我们先分别预处理出来以 1 号点和 n 号点为根的最短路径树（后者需要建反向图），然后考虑每条非树边对于哪些答案存在贡献：
设边为 u->v，则可以翻越从 1 走到 u 所经过的给定链上的最深点的子节点到从 v 走到 n 所经过的给定链上的最浅点。 关于经过的链上最深/浅点如何预处理，可以看代码：

void getd(int u,int from){
    top[u]=from;
    for(foredge(i))
            if(!dep[v]&&edges[i].in) 
                dep[v]=dep[u]+1,getd(v,onlist[v]?v:from);
}

那么对于每条非树边所产生的贡献，可以用线段树来维护。

复杂度分析

使用dijkstra求最短路树时复杂度为 O(m \log m)，线段树复杂度则为 O(n \log n)，总复杂度为 O(m \log m)。

代码

#include <bits/stdc++.h>
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define ll long long
#define UF(i,a,b) for(ll i=a;i>=b;i--)
#define Pii pair<int,int>
#define lc pos<<1
#define rc pos<<1|1
#define foredge(i) int i=head[u],v=edges[i].to;i;i=edges[i].nxt,v=edges[i].to
using namespace std;
const ll N=100005,M=200005;
ll read(){
    ll x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
void write(ll x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void write(ll x,char c){
    if(x<0) putchar('-'),write(-x);
    else write(x);
    putchar(c);
}
int onlst[N];
struct Graph{
    struct Edge{
        int to,nxt,w,in;
        Edge(int a=0,int b=0,int c=0){
            nxt=a,to=b,w=c;
        }
    }edges[N<<1];
    int epos,head[N];
    void add(int u,int v,int w=0){
        edges[++epos]=Edge(head[u],v,w);
        head[u]=epos;
    }
    struct Pos{
        int p,w,from,d;
        Pos(int a=0,int b=0,int c=0){
            p=a,w=b,from=c;
        }
        bool operator<(const Pos &b)const{
            return w>b.w;
        }
    };
    int dis[N],in[N],dep[N],top[N];
    void dij(int s){
        memset(dis,0x3f,sizeof(dis));
        memset(in,0,sizeof(in));
        dis[s]=0;
        priority_queue<Pos> q;
        q.push(Pos(s,0));
        while(!q.empty()){
            Pos nw=q.top();
            q.pop();
            int u=nw.p;
            if(in[u]) continue;
            in[u]=1, edges[nw.from].in=1;//最短路径树边
            for(foredge(i)){
                int tow=nw.w+edges[i].w;
                if(dis[v]>tow){
                    dis[v]=tow;
                    q.push(Pos(v,tow,i));
                }
            }
        }
    }
    void getd(int u,int from){//处理每个点所经过的最值链上点
        top[u]=from;
        for(foredge(i)) if(!dep[v]&&edges[i].in) dep[v]=dep[u]+1,getd(v,onlst[v]?v:from);
    }
}g1,g2;
struct SegmentTree{//线段树维护最小值
    int mn[N<<2],ltag[N<<2];
    void init(){
        memset(mn,0x3f,sizeof(mn));
        memset(ltag,0x3f,sizeof(ltag));
    }
    void up(int pos){
        mn[pos]=min(mn[lc],mn[rc]);
    }
    void down(int pos){
        mn[lc]=min(mn[lc],ltag[pos]),mn[rc]=min(mn[rc],ltag[pos]);
        ltag[lc]=min(ltag[lc],ltag[pos]),ltag[rc]=min(ltag[rc],ltag[pos]);
        ltag[pos]=0x3f3f3f3f;
    }
    void modify(int pos,int l,int r,int tl,int tr,int k){
        if(l>=tl&&r<=tr){
            mn[pos]=min(mn[pos],k), ltag[pos]=min(ltag[pos],k);
            return;
        }
        int mid=l+r>>1;
        down(pos);
        if(mid>=tl) modify(lc,l,mid,tl,tr,k);
        if(mid<tr) modify(rc,mid+1,r,tl,tr,k);
        up(pos);
    }
    int query(int pos,int l,int r,int tl,int tr){
        if(l>=tl&&r<=tr) return mn[pos];
        down(pos);
        int mid=l+r>>1,ans=0x3f3f3f3f;
        if(mid>=tl) ans=min(ans,query(lc,l,mid,tl,tr));
        if(mid<tr) ans=min(ans,query(rc,mid+1,r,tl,tr));
        return ans;
    }
}seg;
int n,m,l;
int q[M];
int main(){//必然是1->x1的最短路+单独的边x1->x2+n->x2的最短路
    n=read(),m=read(),l=read();
    F(i,1,m){
        int u=read(),v=read(),w=read();
        g1.add(u,v,w),g2.add(v,u,w);
    }
    F(i,1,l) q[i]=read(),g1.edges[q[i]].in=1;
    F(u,1,n){
        for(int i=g1.head[u];i;i=g1.edges[i].nxt){
            int v=g1.edges[i].to;
            if(g1.edges[i].in){
                g1.edges[i].in=0;
                onlst[u]=onlst[v]=1;
            }
        }
    }
    g1.dij(1),g2.dij(n);
    g1.dep[1]=1,g1.getd(1,1);
    seg.init();
    //n->x2最短路一定是x2->x3与x3->n,后半部分与给定的1->n链重叠,则预处理出反向图所有点到n经过的链上最高点
    g2.dep[n]=1,g2.getd(n,n);
    F(u,1,n){
        for(int i=g1.head[u];i;i=g1.edges[i].nxt){
            int v=g1.edges[i].to;
            int l=g1.dep[g1.top[u]]+1,r=g1.dep[g2.top[v]];//答案的贡献区间
            if(g1.edges[i].in) continue;
            seg.modify(1,1,n,l,r,g1.dis[u]+g1.edges[i].w+g2.dis[v]);//答案
        }
    }
    F(i,1,l){
        int ans=seg.query(1,1,n,g1.dep[g1.edges[q[i]].to],g1.dep[g1.edges[q[i]].to]);//每条边下放到目标节点
        if(ans<1e9+10) write(ans,'\n');
        else write(-1,'\n');//无解
    }
    return 0;
}