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

4 - Королевство Эльдория

from collections import deque

def bfs(g, s):
    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)
    return d

n, m = map(int, input().split())
s1, s2 = map(int, input().split())
s1 -= 1
s2 -= 1
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if u != v:
        g[u].append(v)
        g[v].append(u)

d1 = bfs(g, s1)
d2 = bfs(g, s2)

ans_time = -1
ans_city = -1
for i in range(n):
    if d1[i] != -1 and d2[i] != -1:
        t = max(d1[i], d2[i])
        if ans_time == -1 or t < ans_time or (t == ans_time and i + 1 < ans_city):
            ans_time = t
            ans_city = i + 1

if ans_time == -1:
    print(-1)
else:
    print(ans_time)
    print(ans_city)

Загрузка...

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

💬

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

Печать