Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1680. Рассылка информации
Минимальное остовное деревоОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (G) |
| 10/01/2023 | Остовные деревья (проводит BOGAT) (C) |
| 05/03/2023 | «Базовая олимпиадная подготовка» (second level) - Остовные деревья (проводит novink) (C) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (3)
Староста группы должна сообщить всем студентам в группе некоторую информацию.
Так как стоимость разговора у разных операторов сотовой связи различна и может отличаться в зависимости от направления вызова,
то необходимо найти способ довести информацию до всех студентов,
потратив минимальные средства. Кроме того не у каждого человека есть номера телефонов
остальных студентов группы (т.е. `a` может позвонить `b`, а `b` может не знать номер телефона `a`).
Напишите программу, которая определит минимальные затраты на информирование студентов.
Первая строка ввода содержит два целых числа – количество студентов `N` (`1\ ≤\ N\ ≤\ 1000`)
и количество каналов связи
между студентами `M` (`1\ ≤\ M\ ≤\ 10000`).
Далее следует `M` строк, содержащих по три целых числа `a`, `b` и `с` (`0\ ≤\ a,\ b\ ≤\ N-1`, `a\ ≠\ b`, `0\ ≤\ c\ ≤\ 1000`),
означающие, что студент `a` может передать информацию студенту `b`, потратив `c` копеек.
Номер 0 соответствует старосте группы. Пары студентов (`a`,`b`) в списке каналов связи не повторяются.
Вывести одно целое число – минимальные затраты на информирование. Если разослать информацию невозможно,
то вывести сообщение "NO SOLUTION" (без кавычек).
Пример ввода 1
4 5 0 1 10 0 2 10 2 0 20 1 3 20 2 3 30
Пример вывода 1
40
Пример ввода 2
2 1 1 0 10
Пример вывода 2
NO SOLUTION
