【题解】LOJ 2209 「HNOI2014」道路堵塞

Problem

给定一个无向图，并且给定一条 $1-n$ 的最短路
问这条路上任意一条道路无法通行时， $1-n$ 的最短路径是多少

Thought

出题人智障系列（abs 已经卡掉标程

删掉路径后跑 $dis$ ，加边松弛

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100010
typedef pair<int, int> p;
p heap[N << 4];
int total;
queue<int> q;
int in[N];
struct edge {
    int t, n, w;
} e[N << 1];
int head[N], tot = 0;
int n, m, l;
int dis[N], road[N], pos[N], sum[N], key[N];
bool ban[N << 1];
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void addedge(int u, int v, int w) {
    e[++ tot] = {v, head[u], w};
    head[u] = tot;
}
void push(p x) {
    heap[++total] = x;
    int temp = total;
    while (heap[temp] < heap[temp / 2] && temp != 1) {
        swap(heap[temp], heap[temp / 2]);
        temp /= 2;
    }
    return;
}
void pop() {
    heap[1] = (p){ 0, 0 };
    heap[1] = heap[total];
    heap[total--] = (p){ 0, 0 };
    int son, temp = 1;
    while ((temp << 1) <= total) {
        son = (temp << 1);
        if (son + 1 <= total && heap[son + 1] < heap[son])
            ++son;
        if (heap[temp] > heap[son])
            swap(heap[temp], heap[son]);
        temp = son;
    }
    return;
}
void spfa(int begin, int id) {
    while (!q.empty()) q.pop();
    q.push(begin);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        in[now] = 0;
        for (int i = head[now]; i; i = e[i].n) {
            if (ban[i])
                continue;
            int to = e[i].t;
            if (dis[to] > dis[now] + e[i].w) {
                dis[to] = dis[now] + e[i].w;
                if (pos[to] && pos[to] > id)
                    push((p){ dis[to] + sum[pos[to]], pos[to] });
                if (!in[to]) {
                    q.push(to);
                    in[to] = 1;
                }
            }
        }
    }
}
int main() {
    n = read();  m = read(); l = read();
    for (int i = 1; i <= m; i++) {
        int a = read(), b = read(), c = read();
        addedge(a, b, c);
    }
    key[1] = 1;
    pos[1] = 1;
    for (int i = 1; i <= l; i++) {
        road[i] = read();
        ban[road[i]] = true;
        key[i + 1] = e[road[i]].t;
        pos[key[i + 1]] = i + 1;
    }
    for (int i = l; i > 0; i--) {
        sum[i] = sum[i + 1] + e[road[i]].w;
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    spfa(1, 1);
    for (int i = 1; i < l; i++) {
        while (total && heap[1].second <= i) pop();
        if (total)
            printf("%d\n", heap[1].first);
        else
            puts("-1");
        dis[e[road[i]].t] = dis[key[i]] + e[road[i]].w;
        spfa(key[i + 1], i + 1);
    }
    while (total && heap[1].second <= l) pop();
    if (total)
        printf("%d\n", heap[1].first);
    else
        puts("-1");
    return 0;
}