import heapq
import random

# Создание графа
graph = {
    1: {2: random.randint(1, 10), 3: random.randint(1, 10), 4: random.randint(1, 10)},
    2: {1: random.randint(1, 10), 5: random.randint(1, 10)},
    3: {1: random.randint(1, 10), 6: random.randint(1, 10)},
    4: {1: random.randint(1, 10), 7: random.randint(1, 10)},
    5: {2: random.randint(1, 10), 8: random.randint(1, 10)},
    6: {3: random.randint(1, 10), 8: random.randint(1, 10)},
    7: {4: random.randint(1, 10), 9: random.randint(1, 10)},
    8: {5: random.randint(1, 10), 6: random.randint(1, 10), 10: random.randint(1, 10), 11: random.randint(1, 10)},
    9: {7: random.randint(1, 10), 11: random.randint(1, 10)},
    10: {8: random.randint(1, 10), 11: random.randint(1, 10)},
    11: {8: random.randint(1, 10), 9: random.randint(1, 10), 10: random.randint(1, 10)}
}

# Симметричные матрицы
matrices = [[0 for _ in range(11)] for _ in range(11)]
for i in range(1, 5):
    for j in range(1, 5):
        matrices[i][j] = graph[i][j]
        matrices[j][i] = graph[i][j]
for i in range(5, 8):
    for j in range(5, 8):
        matrices[i][j] = graph[i][j]
        matrices[j][i] = graph[i][j]
for i in range(8, 12):
    for j in range(8, 12):
        matrices[i][j] = graph[i][j]
        matrices[j][i] = graph[i][j]

# Алгоритм Дейкстры
def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_vertex = heapq.heappop(queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
        # Вывод промежуточных результатов
        print("Visited:", current_vertex)
        print("Distances:", distances)
        print()
    return distances

# Запуск алгоритма Дейкстры с начальной вершиной 1
distances = dijkstra(graph, 1)