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

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):
    row = list(map(int, input().split()))
    g.append(row)

# находим расстояния от реликвии до всех полян
dist = bfs(g, s)

# получаем расстояния до реликвии для Вити и Пита
if dist[v1] == -1:
    dist_v1 = -1
else:
    dist_v1 = dist[v1]

if dist[v2] == -1:
    dist_v2 = -1
else:
    dist_v2 = dist[v2]

# сравниваем
if dist_v1 == -1 and dist_v2 == -1:
    print("infinity")
elif dist_v1 == -1:
    print("Pit")
elif dist_v2 == -1:
    print("Vit")
elif dist_v1 < dist_v2:
    print("Vit")
elif dist_v2 < dist_v1:
    print("Pit")
else:
    print("fifty-fifty")

Загрузка...

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

💬

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

Печать