|
2010-2011
|
Водородный поезд (100 баллов)
Сеть железнодорожных дорог Байтландии является одной из самых передовых и технологичных во всем мире. В настоящее время подходит к концу разработка принципиально новой модели сверхскоростного водородного поезда. Новая модель является весьма экономичной и заметно более быстрой, чем все предыдущие. Однако для полноценного использования водородного поезда требуется провести некоторую модернизацию существующих железнодорожных станций. Модернизация заключается в установке на станциях специальных заправочных блоков, так как новая модель поезда требует частой заправки водородом. На данный момент руководство страны одобрило запуск опытной эксплуатации нового поезда. Именно для этих целей было решено разработать специальный маршрут движения поезда. Для демонстрации преимущества сверхскоростного поезда было решено выбрать самый длинный маршрут. Сеть железных дорог Байтландии состоит из N станций, пронумерованных целыми числами от 1 до N, связанных между собой при помощи N-1 двусторонних железнодорожных путей. Каждый железнодорожный путь связывает ровно две различные станции и имеет определенную длину в километрах. Маршрутом будем называть такую последовательность станций, в которой каждая станция встречается ровно один раз и все соседние станции в этой последовательности связаны между собой железнодорожными путями. Длиной маршрута будем называть сумму длин всех железнодорожных путей, связывающих соседние станции в соответствующей последовательности. Для любых двух станций Байтландии всегда существует хотя бы один маршрут, связывающий их. Ваша задача – определить величину самого длинного маршрута Байтландии.
Рисунок №1.Описание первого примера. N = 7, самый длинный маршрут = {6, 5, 4 2}, длинна = 18. Входные данные Первая строка входного файла содержит одно натуральное число N (2 ≤ N ≤ 32767). Каждая из следующих N-1 строк описывает один железнодорожный путь и состоит из трех чисел Xi Yi Zi (1 ≤ Xi, Yi ≤ N, Xi ≠Yi, 1 ≤ Zi ≤ 65536), разделенных одиночными пробелами, где Xi и Yi – номера станций связанных железнодорожным путем, а Zi – длина соответствующего пути. Выходные данные Выходной файл должен содержать ровно одно целое число – величину самого длинного маршрута Байтландии.
|
