元のグラフで頂点 \(1\) から頂点 \(N\) にたどり着ける場合を考えます。

まず、元のグラフでの頂点 \(1\) から頂点 \(N\) までの最短経路を \(1\) つ求めます。 この最短経路に含まれない辺については、通行止めになったとしても影響がありません。

また、最短経路に含まれる辺は高々 \(N-1\) 本です。よって、最短経路に含まれる辺が通行止めになった場合には、愚直に \(O(N+M)\) で最短距離を求めても全体としては \(O(N(N+M))\) で十分間に合います。

元のグラフで頂点 \(1\) から頂点 \(N\) にたどり着けない場合の例外処理に注意してください。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m; cin >> n >> m;
    vector<vector<int>> G(n, vector<int>(n, -1));
    vector<pair<int,int>> edge(m);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--; b--;
        G[a][b] = i;
        edge[i] = make_pair(a,b);
    }
    vector<int> dis(n,-1); dis[0] = 0;
    vector<pair<int,int>> memo(n);
    queue<int> que; que.push(0);
    while(!que.empty()){
        int i = que.front(); que.pop();
        for(int j = 0; j < n; j++) if(dis[j] == -1 && G[i][j] != -1){
            dis[j] = dis[i] + 1;
            memo[j] = make_pair(i,G[i][j]);
            que.push(j);
        }
    }
    if(dis[n-1] == -1){
        for(int i = 0; i < m; i++) cout << -1 << endl;
        return 0;
    }
    vector<int> shortest_path;
    int cur = n-1;
    while(cur != 0){
        shortest_path.push_back(memo[cur].second);
        cur = memo[cur].first;
    }
    vector<int> ans(m, dis[n-1]);
    for(int e : shortest_path){
        G[edge[e].first][edge[e].second] = -1;
        queue<int> que; que.push(0);
        vector<int> dis(n, -1); dis[0] = 0;
        while(!que.empty()){
            int i = que.front(); que.pop();
            for(int j = 0; j < n; j++) if(dis[j] == -1 && G[i][j] != -1){
                dis[j] = dis[i] + 1;
                que.push(j);
            }
        }
        ans[e] = dis[n-1];
        G[edge[e].first][edge[e].second] = e;
    }
    for(int x:ans)cout << x << endl;
}