Submission #6416533

---

Source Code Expand

#!/usr/bin/env python3
#ABC21 C
#ダイクストラ法

from collections import deque
from heapq import heappush, heappop

mod = 10**9 + 7

def dijkstra():
    #startノードからの最短距離のリスト
    #初期ノードは0,それ以外は無限大で初期化
    distance = [float('inf') for _ in range(n)]
    distance[a] = 0
    #startノードをqueueに入れる
    que = [[0,a]]
    #startから各ノードへの最短経路の数のリスト
    #startノードへの最短経路は1つ
    ans = [0]*n
    ans[a] = 1
    #未探索のノードがあるなら
    while que:
        #優先度(距離)が最小であるqueueを取り出す
        #dx:= startからの距離,x:= ノード
        dx,x = heappop(que)
        #y:= 取り出したノード(x)と辺でつながっているノード
        for y in edge[x]:
            #まだそのノード(y)を見ていないとき
            #startからyまでの距離をdx + 1にする
            if distance[y] > dx + 1:
                distance[y] = dx + 1
                #yまでの最短経路数はxまでの最短経路数と同じ
                ans[y] = ans[x]
                #まだ見ていなかったのでqueueに入れる
                heappush(que,[distance[y],y])
            #一度見ており、1回目とは違うノード(x)からそのノード(y)を見たとき
            #(1回目とノードは違うが、最短距離は同じノード)
            elif distance[y] == dx + 1:
                #yまでの最短経路にxからの経路を加える
                ans[y] += ans[x]
    return ans
n = int(input())
a,b = map(int,input().split())
a -= 1
b -= 1
m = int(input())
xy = [list(map(int,input().split())) for _ in range(m)]
edge = [[] for _ in range(n)]
for x,y in xy:
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
ans = dijkstra()
print(ans[b] % mod)

Submission Info

Judge Result