e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Dijkstra algorithm

Почти кратчайший путь - взвешенный

Поиск кратчайшего пути от начальной точки до конечной, с заданным набором точек и длинами ребер их соединяющих, - уже хорошо известная задача. Это уже часть нашей повседневной жизни, поскольку программы поиска кратчайшего пути широко используются в наше время.

Большинству людей эти приложения нравятся, поскольку они сильно облегчают их жизнь. А может и не сильно.

Сейчас, когда почти каждый имеет доступ к устройствам GPS-навигации, способным рассчитывать кратчайшие пути, большинство маршрутов, образующих кратчайший путь, становятся медленнее из-за интенсивного движения. Поскольку большинство людей пытается следовать по одному и тому же пути, больше не стоит следовать этим указаниям.

Имея это в виду, Ваш начальник просит Вас разработать новое приложение, доступ к которому будет иметь только он. Это сэкономит ему время на встрече или каком-либо срочном мероприятии. Программа должна находить не кратчайший путь, а почти кратчайший путь. Почти кратчайший путь - это такой кратчайший путь от начальной точки до конечной, что ни одно его ребро не принадлежит какому-либо кратчайшему пути между начальной и конечной точками.

На рисунке ниже представлена карта с кругами - точками местоположения, и стрелками - односторонними маршрутами с указанными длинами. Начальная точка отмечена как s, а конечная точка отмечена как d. Жирные линии относятся к кратчайшему пути (в данном случае имеются два кратчайших пути, каждый с суммарной длиной 4). Почти кратчайший путь обозначен пунктирными линиями (суммарная длина 5), поскольку ни один маршрут между двумя последовательными точками не принадлежит ни одному кратчайшему пути. Обратите внимание, что может существовать более одного возможного ответа, например, если маршрут длиной 3 имеет длину 1. Ответ даже может не существовать.

prb10212.gif

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа n (2n500) и m (1m104), обозначающие соответственно количество точек на карте и количество существующих односторонних маршрутов, соединяющих две точки. Каждая точка обозначается целым числом от 0 до n - 1. Вторая строка содержит два целых числа s и d, обозначающих соответственно начальную и конечную точки (sd; 0s, d < n).

Каждая из следующих m строк содержит три целых числа u, v и p (uv, 0u, v < n, 1p103), указывающих на существование одностороннего маршрута из u в v с расстоянием p. Существует не более одного маршрута от точки u до точки v, но обратите внимание, что существование маршрута от u до v не означает, что существует маршрут от v до u, и, если такая дорога существует, она может иметь другую длину. Последняя строка содержит два нуля и не обрабатывается.

Выходные данные

Для каждого теста выведите одну строку, содержащую -1, если невозможно соответствовать требованиям, или целое число, представляющее длину найденного почти кратчайшего пути.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0
Выходные данные #1
5
-1
6