Безбилетный проезд
Вергилий является верным сотрудником агентства тайной национальной безопасности. Каждый день ему приходится тратить много времени на поездки на работу в поезде, в течение которых у него имеется возможность обдумать свое положение и события из жизни. Будучи математиком, он замечает, что хотя он и платит за свои поездки в обязательном порядке, проводники тем не менее редко проверяют его билеты. Имея многолетний опыт, Вергилий имеет достаточно хорошее представление о шансах быть проверенным между каждой парой городов.
Может он сможет увернуться от платы за проезд? Конечно, если его словят в поезде без билета, то придется заплатить штраф, который значительно больше стоимости билета. Но тем не менее... А может дешевле не платить за (часть) путешествие, а выплачивать штрафы когда поймают?
Билет с города A в город B обходится в некоторую начальную стоимость s плюс некоторую небольшую величину p за каждый километр по кратчайшему пути между A и B (билет действителен только по кратчайшему пути). Если Вы пойманы без билета, то следует заплатить штраф, состоящий из некоторой константы y плюс величину p за каждый километр железнодорожного участка пути начиная с последнего города, в котором побывал поезд, и до следующей станции. Правила гласят, что Вы должны выйти на следующей остановке, если вас поймают за безбилетный проезд. Однако будучи сотрудником такого тайного агентства, Вергилий является мастером маскировки: проводники никогда не узнают его, и он может продолжить свое путешествие, как будто он и не был пойман.
Помогите Виргилию написать компьютерную программу, которая базируясь на его опыте найдет путь и даст информацию о билетах, которые следует купить для минимизации его ожидаемых ежедневных затрат^1.
Рассмотрим визуализацию третьего примера. Лучшим вариантом добраться с 1 до 4 - это купить билет на отрезок пути с 1 до 2 стоимостью 20 (10 + 1 × 10), затем проехать зайцем с 2 до 3 с ожидаемой стоимостью 22 (0.1 × (100 + 1 × 120)), и наконец купить билет на отрезок с 3 до 4 стоимостью 20 (10 + 1 × 10). Общая стоимость поездки составит 62 (20 + 22 + 20), которая является наилучшей для заданной железнодорожной сети.
________________________________
^1Ожидаемая ежедневная стоимость проезда составляет E[C] = P_kC_k, где P_k - вероятность того, что стоимость проезда составляет C_k, сумма берется по всем возможным стоимостям. Ожидаемые значения аддитивны, то есть E[X+Y] = E[X] + E[Y].
Входные данные
Первая строка содержит количество тестов, не более 100. Каждый тест состоит из:
одной строки с семью целыми числами:
n (2 ≤ n ≤ 200): количество городов в железнодорожной сети;
m (1 ≤ m ≤ n(n-1)/2): количество прямых соединений в железнодорожной сети;
start (1 ≤ start ≤ n): номер города, в котором живет Виргилий;
end (1 ≤ end ≤ n, start ≠ end): номер города, где работает Виргилий;
s (1 ≤ s ≤ 1000): начальная стоимость билета;
p (1 ≤ p ≤ 1000): стоимость за километр билета или штрафа;
y (s < y ≤ 1000): константная часть штрафа.
m строк с четырьмя целыми числами, задающих двунаправленные дороги между городами. i-ая строка содержит:
a_i (1 ≤ a_i ≤ n): индекс города с одной стороны секции i;
b_i (a_i < b_i ≤ n): индекс города с другой стороны секции i;
c_i (0 ≤ c_i ≤ 100): вероятность того, что кондуктор проверит Ваш билет на секции i, выражаемый в процентах;
d_i (1 ≤ d_i ≤ 1000): длина секции i между городами a_i и b_i в километрах;
Для любой пары (a_i, b_i) и (a_j, b_j) где i ≠ j, имеем (a_i, b_i) ≠ (a_j, b_j).
Выходные данные
Для каждого теста вывести в отдельной строке ожидаемую стоимость поездки между стартовым и конечным городом с двумя десятичными знаками.