Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1903. Союз стран
Кратчайшие пути из одной вершиныОлимпиадные задачи на русском языке
| 30/03/2013 | Южно-Уральский открытый командный чемпионат по программированию (B) |
| 01/04/2013 | Занятие 22 (дорешивание задач командного чемпионата) (A) |
| 16/07/2018 | Лето 2018 - 10 (B) |
| 14/09/2022 | Пути в графах (повторение) (проводит BOGAT) (H) |
| 17/02/2023 | «Базовая олимпиадная подготовка» (second level) - алгоритм Дейкстры (проводит novink) (D) |
Ограничения: время – 4s/8s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Три страны решили объединиться в союзное государство. Так как чиновникам предстоит часто ездить из одной
столицы в другую, необходимо заасфальтировать некоторые дороги (в настоящий момент все дороги являются гравийными)
таким образом, чтобы можно было проехать между двумя любыми столицами по хорошей дороге (необязательно, чтобы
путь был кратчайшим).
Напишите программу, которая определит, какие дороги нужно заасфальтировать, чтобы общая стоимость
строительства была минимальной. Стоимость строительства линейно зависит от длины асфальтируемой дороги.
Формат ввода
Первая строка ввода содержит два целых числа: количество
городов `N` (`3\ ≤\ N\ ≤\ 2000`) и количество дорог `M` (`N-1\ ≤\ M\ ≤\ N*(N-1)/2`). Далее следует `M` строк, содержащих
по три целых числа: номера городов `a_i` и `b_i` (`1\ ≤\ a_i,\ b_i\ ≤\ N`, `a_i\ ≠\ b_i`), связанных гравийной дорогой, и
длина дороги `d_i` (`1\ ≤\ d_i\ ≤\ 10\ 000`). Движение по дорогам возможно в обе стороны. Гарантируется, что
существует путь между двумя любыми городами и в графе нет кратных ребер и петель. Столицами стран являются города с
номерами 1, 2 и 3.
Формат вывода
В первой строке вывести количество асфальтируемых дорог, во второй строке — их номера (от `1` до `M` в соответствии со списком
дорог во входном файле) через пробел в произвольном порядке. Если существует несколько вариантов, минимизирующих
стоимость строительства, можно вывести любой из них.
Пример ввода
6 7 1 6 1 1 3 10 1 5 3 2 5 6 3 4 2 3 5 4 5 6 5
Вывод для примера
3 3 4 6
