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

4 - серверы

from collections import deque

def bfs(start, adj, n):
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        for to in adj[v]:
            if dist[to] == -1:
                dist[to] = dist[v] + 1
                q.append(to)
    return dist

n, m = map(int, input().split())
s1, s2 = map(int, input().split())
s1 -= 1
s2 -= 1

adj = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

dist1 = bfs(s1, adj, n)
dist2 = bfs(s2, adj, n)

best_v = -1
best_time = float('inf')

for v in range(n):
    if dist1[v] != -1 and dist2[v] != -1:
        wait_time = max(dist1[v], dist2[v])
        if wait_time < best_time:
            best_time = wait_time
            best_v = v

if best_v == -1:
    print("НЕТ")
else:
    print(best_v + 1)

Загрузка...

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

💬

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

Печать