Задача №112771. Пожар в НИИЧАВО
В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Корнеева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор \(µ\)-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения \(µ\)-поля.
НИИЧАВО состоит из \(N\) кабинетов, соединённых \(M\) коридорами. Кабинеты пронумерованы целыми числами от 1 до \(N\), при этом кабинет Корнеева имеет номер \(A\), а лаборатория изучения \(µ\)-поля расположена в кабинете номер \(B\). Благодаря специальному искажению пространства внутри института, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.
Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше \(D\) градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магического характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.
Определите, за какое минимальное время можно добраться из кабинета Корнеева до запасной лаборатории, не допуская резкого перепада температур. В рамках данной задачи вам предлагается ответить на поставленный вопрос для нескольких пар значений \(A\) и \(B\).
В первой строке входных данных следуют три целых числа \(N\), \(M\) и \(D\) (\(2 \le N \le 100 000, 1 \le M \le 200 000, 0 \le D \le 2 · 10^8\)), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах.
В последующих \(M\) строках находятся описания коридоров. Каждая строка содержит по три целых числа \(u_i\), \(v_i\), \(t_i\) — номера двух кабинетов, соединённых \(i\)-м коридором, и значение температуры в этом коридоре, выраженное в градусах (\(1 \le u_i, v_i \le N, −10^9 \le t_i \le 10^9\) ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания \(t_i\) .
В следующей строке находится целое число \(Q\) (\(1 \le Q \le 50\)) — количество пар \(A\) и \(B\), которые вам требуется обработать.
В каждой из последующих \(Q\) строк находятся по два целых числа \(A_i\) , \(B_i\) , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (\(1 \le A_i , B_i \le N, A_i ̸= B_i\)).
Для каждого набора данных выведите в отдельной строке минимальное количество минут, которое требуется потратить, чтобы добраться из кабинета Корнеева до лаборатории, либо выведите −1, если сделать это, используя допустимый для дивана-транслятора маршрут, невозможно.
Тесты к этой задаче состоят из 4 групп. Баллы за группы 1 и 2 ставятся только при прохождении всех тестов группы. В группе 3 тесты оцениваются независимо.
Тестирование на группе производится только при прохождении всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
6 9 5 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 2 1 5 4 2
4 -1
6 9 7 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 1 4 2
5