eolymp
bolt
Try our new interface for solving problems
Məsələlər

Happy Birthday

Happy Birthday

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Настал долгожданный день рожденья. Осталось только одно испытание — добраться к Ире домой.

Самый популярный вид транспорта в городе — маршрутки. У каждой маршрутки есть два водителя, один из них любит один маршрут, а второй — другой. Правда место и время отправления маршрутки одинаковы для обоих водителей. Каждый день один из водителей работает, а второй отдыхает. Если Саша окажется на какой-то остановке, то он сразу же узнает, какие из водителей работают сегодня на маршрутках, отправляющихся с этой остановки. Однако до того, как он попадет на остановку, он знает только расписание возможного движения маршруток и вероятность того, что работает первый водитель. Саша живет возле остановки с номером 1 и может оказаться на ней в любое время, а Ира живет рядом с остановкой N. Требуется найти математическое ожидание времени прибытия к Ире на день рожденья. При этом Саша никогда не воспользуется способом, который может привести к тому, что он не попадет к Ире вообще, а среди всех остальных выбирает тот, который минимизирует ожидаемое время прибытия.

Важные факты:

  • Сеть движения маршруток представляет собой ациклический ориентированный граф.

  • С маршрутки на маршрутку можно пересаживаться мгновенно.

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

  • О своей остановке Саша тоже изначально ничего не знает.

Giriş verilənləri

В первой строке даны два числа N и K (2N10^5, 0K10^5) — число остановок и действующих маршруток. Далее в каждой из K строк описана информация о маршруках: семь целых чисел u d p v_1 a_1 v_2 a_2 (1u, v_1, v_2N, uv_1, uv_2, 0d, a_1, a_21440, d < a_1, d < a_2, 0 < p < 100) — номер остановки и время отправления, вероятность того, что работает первый водитель, место и время прибытия, если работает первый водитель, место и время прибытия, если работает второй водитель.

Çıxış verilənləri

Единственное число — математическое ожидание времени прибытия на остановку N с абсолютной или относительной погрешностью 10^{-6} или -1, если есть ненулевая вероятность туда не попасть.

Nümunə

Giriş verilənləri #1
5 6
1 60 50 2 200 3 150
1 100 25 2 160 3 150
1 200 50 5 350 4 300
2 180 50 5 300 4 280
3 400 80 5 600 5 660
4 350 50 5 500 5 550
Çıxış verilənləri #1
423.4375000000000