AtCoder-ABC211 D - Number of Shortest paths 【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210725200115p:plain

AtCoder Beginner Contest211のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 211 - AtCoder

AtCoder Beginner Contest211 D - Number of Shortest paths

D - Number of Shortest paths

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。

道路 i を通ると都市 Ai と都市 Bi の間を双方向に 1 時間で移動することができます。

都市 1 から都市 N へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので (10^9+7) で割ったあまりを求めてください。

制約

・2 ≤ N ≤ 2×10^5
・0 ≤ M ≤ 2×10^5
・1 ≤ Ai < Bi ≤ N
・(Ai,Bi) は相異なる
・入力に含まれる値は全て整数である

解答例

import collections

n, m = map(int,input().split())

graph = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

mod = 10**9 + 7

que = collections.deque()
dist = [-1] * n
cnt = [0] * n
dist[0] = 0
cnt[0] = 1
que.append(0)

while len(que) != 0:
    p = que.popleft()
    for i in graph[p]:
        if dist[i] == -1:
            dist[i] = dist[p] + 1
            que.append(i)
            cnt[i] = cnt[p]
        elif dist[i] == dist[p] + 1:
            cnt[i] += cnt[p]
            cnt[i] %= mod

print(cnt[n-1])