P3238 道路堵塞

· · 题解

第一道黑题，写篇题解纪念一下

[HNOI2014]道路堵塞

题目描述

A国有N座城市，依次标为 1 到 N。同时，在这N座城市间有 M 条单向道路，每条道路的长度是一个正整数。现在，A国交通部指定了一条从城市 1 到城市 N 的路径，并且保证这条路径的长度是所有从城市 1 到城市 N 的路径中最短的。不幸的是，因为从城市 1 到城市 N 旅行的人越来越多，这条由交通部指定的路径经常发生堵塞。现在A国想知道，这条路径中的任意一条道路无法通行时，由城市 1 到 N 的最短路径长度是多少。

输入格式

输入文件第一行是三个用空格分开的正整数 N、M和L ，分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。按下来 M 行，每行三个用空格分开的整数 a、b 和 c ，表示存在一条由城市 a 到城市 b 的长度为 c 的单向道路。这M行的行号也是对应道路的编号，即其中第 1 行对应的道路编号为 1 ，第 2 行对应的道路编号为 2 ，...，第 M 行对应的道路编号为 M 。最后一行为 L 个用空格分开的整数 sp(1)...，，sp(L) ，依次表示从城市 1 到城市N的由交通部指定的最短路径上的道路的编号。

输出格式

输出文件包含L行，每行为一个整数，第 i 行 (i=1，2...，，L) 的整数表示删去编号为 sp(i) 的道路后从城市1到城市N的最短路径长度。如果去掉后没有从城市1到城市N的路径，则输出 -1。

样例 #1

样例输入 #1

4 5 2
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 5

样例输出 #1

6
6

提示

所有的数据满足 2<N<100000，1<M<200000 。所用道路长度大于 0 小于 10000。

数据已加强By Vfleakin。

这是一个图……

我们来康康，首先最短路肯定是1-4-5-7。

按题所说，如果我们删掉1到4这条边，此时最短路变成1-2-4-5-7。

如果我们删掉4到5这条边，此时最短路变成-1。

如果我们删掉7到5这条边，此时最短路变成1-4-5-6-7。

于是我们惊讶的发现，每一条删完边后的最短路径有且仅有一个连续的区间在最短路外。

这只是一个小小的猜测，接下来我们来证明他。

记每一条删完边后的最短路径中的点 ∈ l 。

假设l有两个以上连续的区间在最短路径外，则此时两个以上中的一个区间明显比最短路短，此时矛盾。

假设l与最短路不重合，则由于起点终点相同必有重合，故矛盾。

所以原命题得证。

此时我们从 1 号点开始跑最短路，一遍 SPFA 即可（注意不能经过最短路径上的边）。

然后我们枚举最短路径上的点，把当前它的编号和离终点的距离丢进一个小根堆里。

如果堆的顶部的点在最短路上的位置在当前枚举的的边前，此时就弹出。最后把枚举的这条边加进原图，更新 dist。

代码：

#include<stdio.h>
#include<queue>
#include<memory.h>
using namespace std;
const int N = 200010,M = 400100;
typedef struct{
    int to;
    int val;
}node;
int nxt[M],head[M],ver[M],edg[M],tot=0;
int ssspE[M],ssspV[M],pv[M],dist[N],ID[M],cut[N];
int n,m,l,x,y,z,u,v,w,vis[N];
priority_queue<node> heap;
bool operator <(const node &a,const node &b ){
    return a.val > b.val;
}
void add_v(int x,int y,int z){
    ver[++tot] = y;
    edg[tot] = z ;
    nxt[tot] = head[x];
    head[x] = tot;
}
void spfa(int s){
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while(q.size()){
        int x = q.front();q.pop();
        vis[x] = 0;
        for (int i = head[x] ; i ; i = nxt[i] ){
            if ( cut[i] ) continue;
            int y = ver[i];
            if ( dist[y] > dist[x] + edg[i] ){
                dist[y] = dist[x] + edg[i];
                if ( ID[y] ) heap.push({ID[y],dist[y]+pv[ID[y]]});
                else if ( !vis[y] ) {vis[y] = 1,q.push(y);}
            }
        }

    }
}
int main(){
    //freopen("testdata.in","r",stdin);
    memset(dist,0x3f,sizeof(dist));
    scanf("%d%d%d",&n,&m,&l);
    for (int i = 1 ; i <= m ; i ++ ) {scanf("%d%d%d",&u,&v,&w);add_v(u,v,w);}
    for (int i = 1 ; i <= l ; i ++ ){
        scanf("%d",&ssspE[i]);
        ssspV[i + 1] = ver[ssspE[i]],cut[ssspE[i]] = 1,ID[ssspV[i+1]] = i + 1;
    }
    for (int i = l ; i >= 1 ; i -- ) pv[i] = pv[i+1] + edg[ssspE[i]];
    ID[1] = 1,dist[1] = 0;ssspV[1] = 1;
    spfa(1);
    for (int i = 1 ; i <= l ; i ++ ){
        while(heap.size() && heap.top().to<=i) heap.pop();
        if ( heap.size() ) printf("%d\n",heap.top().val);
        else puts("-1");
        dist[ssspV[i+1]] = dist[ssspV[i]] + edg[ssspE[i]];
        spfa(ssspV[i+1]);
    }
    return 0;
}

完结撒花！