题目描述

难度分:$1753$

输入$n(2 \leq n \leq 400)$，$m(1 \leq m \leq n \times (n-1))$，表示一个$n$点$m$边的有向图。保证图中无自环和重边。

然后输入$m$条边，每条边输入x y，表示一条$x$到$y$的有向边，边权为$1$。节点编号从$1$开始。

输出$m$个数，其中第$i$个数表示删除输入的第$i$条边后，从$1$到$n$的最短路长度。如果无法从$1$到达$n$，输出$-1$。

输入样例$1$

3 3
1 2
1 3
2 3

输出样例$1$

1
2
1

输入样例$2$

4 4
1 2
2 3
2 4
3 4

输出样例$2$

-1
2
3
2

输入样例$3$

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

输出样例$3$

1
1
3
1
1
1
1
1
1
1

输入样例$4$

4 1
1 2

输出样例$4$

-1

算法

BFS+分情况讨论

本题是无权图，所以求最短路用BFS就可以了。我们先从$1$开始进行BFS，求出$1$到所有其他节点的最短路，在求的过程中将前驱节点保留在$from$数组中，也就是说$from[u]=v$表示在最短路上$u$的前面是$v$。然后从$n$节点开始，利用$from$数组追到起点$1$，这样就能得到一条最短路$path$，将这条最短路上的边$id$都存入到一个哈希集合$path$中。

遍历$i \in [1,m]$，判断每条边的答案：

1. 如果$i$不在$path$上，那说明最短路不受$i$这条边的影响，删边之前$1$到$n$的距离是多少就是多少。
2. 如果$i$在$path$上，就重新跑一遍BFS，在这个过程中忽略$i$这条边得到一个最短路。

复杂度分析

时间复杂度

这个算法乍一看感觉会超时，但实际上非常巧妙。由于$1$到$n$的最短路最长也就是$n-1$，所以重新进行BFS的次数最多也就是$O(n)$级别，而每次BFS求最短路时间复杂度为$O(n+m)$。大部分情况下$O(1)$就能得到答案。因此，整个算法的时间复杂度为$O(n(n+m)+m)$。

空间复杂度

图的邻接表空间占用是$O(n+m)$。$from$数组、$dist$数组空间占用为$O(n)$。还需要一个$edge2id$数组，是个$O(n^2)$的数组，$edge2id[u][v]$表示边$uv$的编号。因此，整个算法的额外空间复杂度为$O(n^2+n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 401, INF = 0x3f3f3f3f;
vector<int> graph[N];
int n, m, from[N], dist[N], edge2id[N][N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
        dist[i] = INF;
    }
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        edge2id[u][v] = i;
    }
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nxt: graph[cur]) {
            if(dist[nxt] > dist[cur] + 1) {
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
                from[nxt] = cur;
            }
        }
    }
    unordered_set<int> path;
    int cur = n;
    while(1) {
        int pre = from[cur];
        if(pre == 0) break;
        int index = edge2id[pre][cur];
        cur = pre;
        path.insert(index);
        if(cur == 1) break;
    }
    int ans = dist[n];
    for(int i = 1; i <= m; i++) {
        if(path.count(i)) {
            for(int j = 1; j <= n; j++) {
                dist[j] = INF;
            }
            q.push(1);
            dist[1] = 0;
            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                for(int nxt: graph[cur]) {
                    if(edge2id[cur][nxt] == i) continue;
                    if(dist[nxt] > dist[cur] + 1) {
                        dist[nxt] = dist[cur] + 1;
                        q.push(nxt);
                    }
                }
            }
            printf("%d\n", dist[n] == INF? -1: dist[n]);
        }else {
            printf("%d\n", ans == INF? -1: ans);
        }
    }
    return 0;
}