Submission #2692541

---

Source Code Expand

N = int(input())
a, b = map(int, input().split())
a, b = a-1, b-1
M = int(input())
G = [[float('inf')]*N for i in range(N)]
edge = []
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    G[x][y] = 1
    G[y][x] = 1
    edge.append((x, y))

for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k]+G[k][j])

P = G[a]
P[a] = 0
DAG = [[] for i in range(N)]
for x, y in edge:
    if P[y] == P[x] + 1:
        DAG[x].append(y)
    if P[x] == P[y] + 1:
        DAG[y].append(x)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


topology = topological_sort(DAG)
dp = [0] * N
dp[a] = 1
for t in topology:
    for e in DAG[t]:
        dp[e] += dp[t]

print(dp[b] % (10**9+7))

Submission Info

Judge Result