ABC218F - Blocked Roads

考え方

1. 辺を除かない状態で，最短距離dを求める．また，最短経路につかう辺の集合routeを求める．
2. 辺を順に除いていき，その辺がrouteに含まれないならdが答え．routeに含まれるなら，もう一度最短距離を求める（※）．

（※）routeの数≦$N-1$で，最短経路の計算量がすべての辺と頂点をみて$O(N+M)$なので間に合う．

【参考】
Submission #25762549 - AtCoder Beginner Contest 218

回答例

from collections import deque
INF = 1000

N, M = map(int, input().split())
G = [[] for _ in range(N)]
E = []

for _ in range(M):
  s, t = map(int, input().split())
  s -= 1
  t -= 1
  G[s].append(t)
  E.append((s, t))
  
dist = [INF] * N
prev = [[] for _ in range(N)]
dist[0] = 0
que = deque([0])
while que:
  cur = que.popleft()
  for chi in G[cur]:
    if dist[cur] + 1 < dist[chi]:
      dist[chi] = dist[cur] + 1
      prev[chi] = cur
      que.append(chi)
      
if dist[-1] == INF:
  for _ in range(M):
    print(-1)
  exit()
  
route = set()
cur = N - 1
while cur != 0:
  par = prev[cur]
  route.add((par, cur))
  cur = par
  
for e in E:
  if e not in route:
    print(dist[-1])
    continue
  dist2 = [INF] * N
  dist2[0] = 0
  que = deque([0])
  while que:
    cur = que.popleft()
    for chi in G[cur]:
      if (cur, chi) == e:
        continue
      if dist2[cur] + 1 < dist2[chi]:
        dist2[chi] = dist2[cur] + 1
        que.append(chi)
  print(dist2[-1] if dist2[-1] < INF else -1)