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

"РАДИУС ДЕЙСТВИЯ" Условие: В городе есть N районов и M дорог. В районе X открывается скорая помощь, которая может доехать не более чем до районов на расстоянии R. До скольких районов (включая свой) может доехать скорая?

n, m, x, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n + 1)
queue = [x]
dist[x] = 0
idx = 0

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

count = 0
for i in range(1, n + 1):
    if dist[i] != -1 and dist[i] <= r:
        count += 1

print("Скорая может доехать до", count, "районов")

Загрузка...

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

💬

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

Печать