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

4

from collections import deque

# Чтение данных
n, k, s = map(int, input().split())
exits = list(map(int, input().split()))
m = int(input())

# Создаём граф
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# BFS от комнаты друга
dist = [-1] * (n + 1)
queue = deque([s])
dist[s] = 0

while queue:
    v = queue.popleft()
    for to in graph[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            queue.append(to)

# Ищем ближайший выход
best_exit = exits[0]
min_dist = dist[best_exit]

for exit_room in exits:
    if dist[exit_room] != -1:
        if dist[exit_room] < min_dist or (dist[exit_room] == min_dist and exit_room < best_exit):
            min_dist = dist[exit_room]
            best_exit = exit_room

print(best_exit)

Загрузка...

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

💬

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

Печать