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

4 - Петя ЛКШ

def bfs(g, start):
    dist = [-1] * len(g)
    dist[start] = 0
    queue = [start]
    while queue:
        v = queue.pop(0)
        for nxt in range(len(g)):
            if g[v][nxt] == 1 and dist[nxt] == -1:
                dist[nxt] = dist[v] + 1
                queue.append(nxt)
    return dist

n, s, v1, v2 = map(int, input().split())
s -= 1
v1 -= 1
v2 -= 1

g = []
for i in range(n):
    g.append(list(map(int, input().split())))

dist = bfs(g, s)

# если до умывальника можно дойти по коридорам, то нарядов = количество коридоров
# если нельзя, то Петя воспользуется потайным ходом и получит 10000 нарядов
if dist[v1] == -1:
    cost1 = 10000
else:
    cost1 = dist[v1]

if dist[v2] == -1:
    cost2 = 10000
else:
    cost2 = dist[v2]

if cost1 < cost2:
    print(1)
else:
    print(0)

Загрузка...

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

💬

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

Печать