Статья Автор: Дубинин Дмитрий

Поиск количества кратчайших путей в невзвешенном графе

MOD = 10**9 + 7

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

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

dist = [-1] * (n + 1)
ways = [0] * (n + 1)

queue = [1]
dist[1] = 0
ways[1] = 1

idx = 0
while idx < len(queue):
    v = queue[idx]
    idx += 1
    
    for to in graph[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            ways[to] = ways[v]
            queue.append(to)
        elif dist[to] == dist[v] + 1:
            ways[to] = (ways[to] + ways[v]) % MOD

if dist[n] == -1:
    print(0)
else:
    print(ways[n] % MOD)

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать