Submission #3005049

---

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][0] > w:
			heapq.heappush(q, [w,t])
			weight[t][0] = w


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

weight.sort()

cnts = [0]*N
cnts[Start] = 1
for w,i in weight:
	n = cnts[i]
	for t,nyan in list(lines[i]):
		if weight[t][0] == weight[i][0]+1:
			cnts[t] += n

print(cnts[Goal])

Submission Info

Judge Result