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

4 - Участники квеста

from collections import deque

def bfs(g, s, exits):
    d = [-1] * len(g)
    d[s] = 0
    q = deque([s])
    while q:
        v = q.popleft()
        for to in g[v]:
            if d[to] == -1:
                d[to] = d[v] + 1
                q.append(to)
    mn = float('inf')
    for e in exits:
        if d[e] != -1:
            mn = min(mn, d[e])
    return mn

n, k, s = map(int, input().split())
s -= 1
exits = list(map(int, input().split()))
for i in range(k):
    exits[i] -= 1
m = int(input())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

mn = bfs(g, s, exits)
if mn == float('inf'):
    print(-1)
else:
    t = mn * 2
    if t <= 10:
        print(t)
    else:
        if t % 10 == 0:
            print(t)
        else:
            print(((t - 1) // 10 + 1) * 10)

Загрузка...

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

💬

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

Печать