Статья Автор: Федотова Анна

4

Это из гугла

import collections

# Чтение данных
N, K, S = map(int, input().split())
exits = set(map(int, input().split()))
M = int(input())
adj = collections.defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

# BFS
dist = {S: 0}
queue = collections.deque([S])

while queue:
    curr = queue.popleft()
    curr_time = dist[curr]
    
    # Проверка: открыты ли двери?
    # Период 20 сек: 0-10 открыто, 10-20 закрыто
    if (curr_time // 10) % 2 == 1:
        start_time = (curr_time // 10 + 1) * 10
    else:
        start_time = curr_time
        
    arrival_time = start_time + 2
    
    for neighbor in adj[curr]:
        if neighbor not in dist or dist[neighbor] > arrival_time:
            dist[neighbor] = arrival_time
            queue.append(neighbor)

# Ответ
ans = min(dist[e] for e in exits if e in dist)
print(ans)

Загрузка...

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

💬

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

Печать