Задача №112650. Электрификация
В Простоквашино решили провести электрификацию: подвести электричество ко всем домам. При этом точки стыковки линий электропередач могут находиться только около домов (линии не могут пересекаться и разветвляться в поле). Электростанция тоже находится около одного из домов. Напишите программу, которая строит сеть линий электропередач минимальной общей длины в Простоквашино.
В первой строке вводится количество домов N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему возможных соединений домов. Число в матрице обозначает расстояние между домами, ноль – линию провести невозможно.
Программа должны вывести все пары номеров домов, между которыми нужно построить линии электропередач. Нумерация домов начинается с единицы. Они должны быть отсортированы следующим образом. В каждой паре сначала записывается меньший номер дома, потом – больший. Среди пар сначала идут пары с меньшим первым номером, среди них – сначала пары с меньшими вторыми номерами домов. Если при построении схемы на каком-то этапе можно выбрать несколько равноценных вариантов соединения, то выбирается тот, где номер первого дома меньше, а при одинаковом номере первого дома - тот, у которого номер второго дома меньше.
6 0 2 4 0 0 0 2 0 1 0 0 0 4 1 0 5 6 0 0 0 5 0 2 1 0 0 6 2 0 3 0 0 0 1 3 0
1 2 2 3 3 4 4 5 4 6