abc218 F – Blocked Roads

题意：

边权为1的有向简单图，对每条边，问删除该边后 \(1\to n\) 的最短路长度

\(n\le 400\)

思路：

这题不会做，感觉我该重读幼儿园

bfs 的复杂度是 \(n^2\)

先 bfs 随便找一条 \(1\to n\) 的最短路 \(path\)

对边 \(e\)，若 \(e\) 不在 \(path\) 中，则输出 \(path\) 的长度；否则去掉 \(e\) 重新 bfs 找最短路

\(path\) 里的边是 \(O(n)\) 级别的，所以复杂度 \(O(n^3)\)

const int N = 405;
int n, m;
vector<pair<int, int> > G[N];
pair<int, int> pre[N * N];
bool way[N * N];

int bfs(int del = 0) {
    queue<int> q; q.push(1);
    vector<int> d(n + 1, -1); d[1] = 0;
    while(q.size()) {
        auto u = q.front(); q.pop();
        for(auto [v, i] : G[u]) if(i != del && d[v] == -1)
            d[v] = d[u] + 1, q.push(v), pre[v] = {u, i};
    }
    return d[n];
}

void sol() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back({y, i});
    }
    
    int ans = bfs(), now = n;
    while(now > 1)
        way[pre[now].second] = true, now = pre[now].first;
    
    for(int i = 1; i <= m; i++)
        cout << (way[i] ? bfs(i) : ans) << '\n';
}