Задача 8
Дима + картошка = физика! (Авторская задача)
Приведем пример задачи, где может быть использован алгоритм Флойда.
Максимальное время работы на одном тесте: | 2 секунды |
Максимальный объем используемой памяти: | 64 мегабайта |
Жил был на свете Дима Голова. У него, как всем известно, очень суровый отец: не разрешает ну ни сколечко пошалить сыну, а наоборот, заставляет много учиться, работать и заниматься. И вот однажды он сказал Диме, чтобы тот разнес родственникам по мешку картошки. Известно, что изначально вся картошка может быть привезена фурой только в одно место, в то, которое скажет Дима. Из него он начнет свою работу. После того, как он выполнит задание отца, тот ему даст вознаграждение в виде интересной книги по физике, которую Дима сможет забрать в том доме, где изначально была выгружена картошка.
У послушного Димы есть план города, на котором отмечены все дома родственников. Между некоторыми из них есть дороги, и известно, что из любого дома по этим дорогам можно добраться в любой другой дом и что движение в городе только одностороннее. Дима ещё маленький мальчик, поэтому он может взять с собой не более 1-го мешка. По данным плана Дима быстро смог сообразить, в какой именно дом необходимо изначально доставить картошку, чтобы суммарное расстояние, которое ему придется пройти, было минимально, а также найти это расстояние. А вам слабо?
Формат входных данных.
В первой строке записаны числа n и m (1 <= n <= 100; n - 1 <= m < 1000) – число домов и число дорог соответственно.
Далее в m строках расположены описания дорог: 3 целых числа si, ei, li - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 <= si, ei <= N0li100, дороги двунаправленные).
Формат выходных данных.
На выходе программы должно быть 2 числа: номер дома, куда следует привозить картошку, и длину всего пути, который предстоит пройти Диме. Если вариантов ответа несколько, выведите один из них.
Примеры.
in | out |
3 2 1 2 1 2 3 2 | 2 6 |
4 5 1 2 6 2 3 4 4 3 4 1 3 10 4 2 1 | 2 22 |
