Submission #3005262

---

Source Code Expand

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
Start,Goal = inpl()
Start -= 1
Goal -= 1
M = int(input())

lines = defaultdict(set)
for i in range(M):
	a,b = inpl() #a <-> b コスト:c
	a,b = a-1,b-1
	lines[a].add((b,1))
	lines[b].add((a,1))

def search (s,w_0): #s->t
	global weight
	global q

	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w


weight = [INF for i in range(N)]
weight[Start] = 0
q = [[0,Start]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

DAG = defaultdict(set)
for s in range(N):
	for t,c in lines[s]:
		if weight[t]-weight[s] == 1:
			DAG[s].add(t)

ans = 0
memo = [-1]*N
def azunyan(s):
	global ans

	if s == Goal:
		return 1
	elif memo[s] >= 0:
		return memo[s]
	else:
		cnt = 0
		for t in DAG[s]:
			cnt += azunyan(t)
		memo[s] = cnt
		return cnt


print(azunyan(Start)%mod)

Submission Info

Judge Result