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

"РАССТОЯНИЕ МЕЖДУ ВСЕМИ ПАРАМИ ВЕРШИН" Условие: Для каждой пары вершин найти расстояние между ними (матрица расстояний).

n, m = 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)

def bfs(start):
    dist = [-1] * (n + 1)
    queue = [start]
    dist[start] = 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)
    return dist

# Создаём матрицу расстояний
distance_matrix = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    d = bfs(i)
    for j in range(1, n + 1):
        distance_matrix[i][j] = d[j]

# Выводим матрицу
print("Матрица расстояний:")
for i in range(1, n + 1):
    for j in range(1, n + 1):
        print(distance_matrix[i][j], end=" ")
    print()

Загрузка...

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

💬

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

Печать