Problem 2: Roadblock [Brian Dean]
Каждое утро Фермер Джон по ферме от своего дома к амбару. Ферма это коллекция из N полей (1<=N<=250), соединённых M двунаправленными дорожками (1<=M<=25,000) определённой длины. Дом фермера находится на поле 1, а амбар – на поле N. Никакие два поля не соединены более чем одной дорожкой. И существует путь (как последовательность дорожек) из любого поля к любому. Перемещаясь от поля к полю, ФД всегда выбирает маршрут, состоящий из последовательности дорожек, имеющих наименьшую общую длину. Коровы «вредничают». Они планируют построить стог сена ровно на одной из M дорожек, тем самым увеличив вдвое её длину. Коровы хотят выбрать такую дорожку, чтобы максимизировать увеличение маршрута ФД от дома к амбару. Помогите коровам определить, насколько они могут удлинить маршрут ФД.
PROBLEM NAME: rblock
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..1+M: Строка j+1 описывает j-ую двунаправленную дорожку тремя разделёнными пробелами числами Aj Bj Lj, где Aj и Bj это числа в диапазоне1..N, указывающие поля, соединённые этой дорожкой, а L – длина этой дорожки (в диапазоне 1...1,000,000).
Формат выходных данных
* Строка 1: Максимально возможное увеличение длины кратчайшего маршрута ФД, которого можно достичь удвоением длины одной дорожки.
Примечание
Если коровы удвоят длину дорожки из поля 3 в поле 3 (от 3 до 6), тогда кратчайший маршрут ФД станет 1-3-5 с длиной 1+7=8, что увеличивает на 2 первый кратчайший путь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
|
2
|