Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 256 Мб | |
Максимальный балл: | 100 |
Экспедиция, в которую входит лейтенант О'Денил, собирается отправиться в далекую звездную систему F из системы S. Но ограничения на количество топлива в корабле не позволяют лететь напрямую по назначению, так что приходится делать дозаправки в других системах не реже, чем через T лет. Чтобы максимально быстро преодолевать межзвездные расстояния, половину пути корабль летит равноускоренно с ускорением a=1св.год/год2, а вторую половину равнозамедленно с тем же ускорением, что позволяет останавливаться вовремя. Дозаправки, по сравнению с перелетами, происходят моментально. Кроме того, из-за космических опасностей возможны перелёты только по заданным переходам.
Необходимо определить, за какое минимальное время исследователи могут добраться до своей цели.
Примечания:
Если корабль начал движение с нулевой начальной скоростью, то расстояние, пройденное им за время t с ускорением a, следует считать по формуле at22.
Световой год - расстояние, которое свет проходит в вакууме за один год.
В первой строке вводится целое число T – максимальное время перелета между системами в годах.
Во второй строке вводится 3 целых числа: количество известных звездных систем N, номер начальной звездной системы S и номер конечной F (S≠F).
В третьей строке вводится количество безопасных переходов между различными соседними системами M. Остальные M строк содержат описания переходов в виде трех целых чисел ai, bi, li, где ai и bi - номера систем, а li - расстояние между системами в световых годах 1≤li≤109.
Выведите единственное число - минимально возможное время полета в годах, с точностью не менее двух десятичных знаков.
1≤ai,bi≤N
1≤i≤M
2≤N≤50
1≤S,F≤N
1≤M≤N⋅(N−1)2
1≤li≤109
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|