以前の記事で ABC167-D について扱いました。ここで出題された問題は幅優先探索を用いることによって綺麗に解くことができました。今回はほぼ同様の実装で解くことのできる例題を見つけたので扱ってみたいと思います。
問題の概要
$N$ 個の町（町 $1,$ 町 $2,\dots ,$ 町 $N$）と $M$ 本の道路（道路 $1,$ 道路 $2,\dots ,$ 道路 $M$）があります。道路は二つの町を双方向につないでおり、すべての道路は同じ時間で移動が可能です。このとき、町 $a$ から町 $b$ への最短経路が何通りあるかについて、答えを $10^9 + 7$ で割った余りを求めてください。問題のURL
制約
- $2 \leqq N \leqq 100$
- $1 \leqq M \leqq 200$
解法
幅優先探索で探索をしながら経路を数えていきます。
from collections import deque
n = int(input())
a, b = map(int, input().split())
a, b = a - 1, b - 1 # 0-index
m = int(input())
adj = [[] for _ in range(n)] # 隣接リスト
for i in range(m):
x, y = map(int, input().split())
x, y = x - 1, y - 1 # 0-index
adj[x].append(y)
adj[y].append(x)
MOD = 10 ** 9 + 7
# 頂点 a からすべての頂点への最短距離を求める
q = deque()
q.append(a) # 頂点 a をenque
INF = 10 ** 9
dist = [INF] * n # INF で初期化
dist[a] = 0 # 始点から始点の距離 = 0
dp = [0] * n # 求める組み合わせ
dp[a] = 1 # 始点から始点は 1 通り
while q:
u = q.popleft() # queueから取り出す（deque）
for to in adj[u]: # 隣接している頂点について
if dist[to] == INF:
dist[to] = dist[u] + 1
dp[to] += dp[u]
dp[to] %= MOD
q.append(to)
elif dist[to] == dist[u] + 1:
dp[to] += dp[u]
dp[to] %= MOD
print(dp[b])
