D - Number of Shortest paths
皆さん、こんにちは！
ハリーです。今回も BFS（幅優先探索）に関連する問題を解いていきたいと思います。いつまで続けるのかって？私が BFS マスターになるまでです！それでは、解いていきましょう！
D - Number of Shortest paths
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。
道路 $i$ を通ると都市 $Ai$ と都市 $Bi$ の間を双方向に1時間で移動することができます。
都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので $(10^9 + 7)$ で割ったあまりを求めてください。
制約
- $2 \leq N \leq 2 × 10^5$
- $0 \leq M \leq 2 × 10^5$
- $1 \leq Ai < Bi \leq N$
- $( Ai, Bi ) $は相異なる
- 入力に含まれる値は全て整数である
入力例1
4 5 2 4 1 2 2 3 1 3 3 4
出力例1
2
入力例2
4 3 1 3 2 3 2 4
出力例2
1
入力例3
2 0
出力例3
0
入力例4
7 8 1 3 1 4 2 3 2 4 2 5 2 6 5 7 6 7
出力例4
4
実装方法
まず初めに、collections ライブラリのimport を行います。
from collections import deque
次に、入力を受け取ります。
まず、NとMの値の入力を受け取り、道路によってつながっている都市を保存する graph 配列を用意します。
n, m = map(int,input().split())
graph = [ for _ in range(n)]
道路によってつながっている都市の入力を受け取り、0-index に値を合わせ 配列 graph に値を入れていきます。
for i in range(m):
a, b = map(int,input().split())
a = a - 1
b = b - 1
graph[a].append(b)
graph[b].append(a)
割ったあまりを出すために mod を用意します。
mod = 10**9 + 7
deque オブジェクトを生成します。そして、最短距離を表すdist 配列と経路の数を表すcnt 配列を作成し、初期値を入れます。
q = deque()
dist = [-1] * n
dist[0] = 0
cnt = [0] * n
cnt[0] = 1
q.append(0)
キューからpopした都市から遷移できる都市が未到達の場合は、移前の距離に1を足して更新します。遷移できる都市jが到達済みの場合でも、最短距離 dist の値が同じであれば cnt[ j ] に遷移前の数を足し合わせることで最短経路の数を更新していきます。
while q:
p = q.popleft()
for i in graph[p]:
if dist[i] == -1:
dist[i] = dist[p] + 1
q.append(i)
cnt[i] = cnt[p]
elif dist[i] == dist[p] + 1:
cnt[i] += cnt[p]
cnt[i] %= mod
最後に、都市Nまでの最短経路の数 cnt[n-1]を出力すれば終了です。
print(cnt[n-1])
ACコード
from collections import deque
n, m = map(int,input().split())
graph = [ for _ in range(n)]
for i in range(m):
a, b = map(int,input().split())
a = a - 1
b = b - 1
graph[a].append(b)
graph[b].append(a)
mod = 10**9 + 7
q = deque()
dist = [-1] * n
dist[0] = 0
cnt = [0] * n
cnt[0] = 1
q.append(0)
while q:
p = q.popleft()
for i in graph[p]:
if dist[i] == -1:
dist[i] = dist[p] + 1
q.append(i)
cnt[i] = cnt[p]
elif dist[i] == dist[p] + 1:
cnt[i] += cnt[p]
cnt[i] %= mod
print(cnt[n-1])
最後に
どうでしたでしょうか？今回も今までやってきたことの応用のような問題でしたね。
早くコンテストで BFS の問題が出題されてほしいです！今週もお疲れ様でした！
それでは皆さん、また来週！
