AtCoder ABC218F. Blocked Roads(青色)
原题链接
中等
算法
(bfs求最短路) $O(MN)$
- 若被删去的边不在最短路上将不会影响答案
- 对于 $1 \to N$ 的最短路最多经过 $N - 1$ 条边,所以对于被删的边出现在最短路上,则可以以 $O(N)$ 的时间求出
- 我们在第一次求最短路的时候可以记录一下所遍历过的边,然后只需对在删除这些边的前提下跑最短路即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
struct Edge {
int to, id;
Edge() {}
Edge(int to, int id): to(to), id(id){}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<Edge>> g(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].emplace_back(b, i);
}
const int INF = 1001001001;
vector<int> es;
auto bfs = [&](int ng = -1) {
vector<int> dist(n, INF);
vector<int> pre(n, -1);
vector<int> pre_id(n, -1);
queue<int> q;
q.push(0); dist[0] = 0;
while (q.size()) {
int v = q.front(); q.pop();
for (auto e : g[v]) {
if (e.id == ng) continue;
if (dist[e.to] != INF) continue;
dist[e.to] = dist[v] + 1;
pre[e.to] = v; pre_id[e.to] = e.id;
q.push(e.to);
}
}
if (dist[n - 1] == INF) return -1;
if (ng == -1) {
int v = n - 1;
while (v != 0) {
es.push_back(pre_id[v]);
v = pre[v];
}
}
return dist[n - 1];
};
int base = bfs();
vector<int> ans(m, base);
for (int i : es) ans[i] = bfs(i);
rep(i, m) cout << ans[i] << '\n';
return 0;
}