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

"BFS ДЛЯ ВЗВЕШЕННОГО ГРАФА (0-1 BFS)" Условие: В графе есть рёбра веса 0 и 1. Найти кратчайшее расстояние от A до B.

from collections import deque

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

for _ in range(m):
    x, y, w = map(int, input().split())  # w - вес ребра (0 или 1)
    graph[x].append((y, w))
    graph[y].append((x, w))

dist = [10**9] * (n + 1)
dist[a] = 0
dq = deque()
dq.appendleft(a)

while dq:
    v = dq.popleft()
    for to, w in graph[v]:
        if dist[v] + w < dist[to]:
            dist[to] = dist[v] + w
            if w == 0:
                dq.appendleft(to)
            else:
                dq.append(to)

print(dist[b])

Загрузка...

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

💬

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

Печать