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;
}