Планувальник доріг
Ациклічна дорожня мережа складається з односторонніх дорожніх сегментів (ребер), кожен з яких з'єднує два перехрестя (вершини) з загальної кількості N перехресть. Час, необхідний для подолання дорожнього сегмента, завжди позитивний і залежить лінійно від кількості автомобілів C, що використовують сегмент s:
T(s) = a_S C + b_S
a_S та b_S — це дві константи, виражені у вигляді чисел з плаваючою комою одинарної точності, що описують властивості дорожнього сегмента s. Час, необхідний для перетину перехрестя, дорівнює 0.
Кількість автомобілів повинна проїхати від вершини 0 до вершини N-1 у цій дорожній мережі. Кожен автомобіль обирає свій маршрут егоїстично, щоб зменшити свій власний час подорожі; кожен автомобіль знає, що всі інші автомобілі також егоїстично обиратимуть свій маршрут. Вам потрібно написати програму, яка обчислює, скільки автомобілів проїде кожним з можливих шляхів від джерела до пункту призначення, і час, необхідний для подорожі цими шляхами.
Вхідні дані
Вхідний файл містить кілька тестів і організований наступним чином. Перша строка містить кількість тестів. Наступні строки містять специфікацію тестів. Кожен тест містить у першій строку кількість вершин, кількість ребер і кількість автомобілів, розділених пробілами. Після цього кожне ребро подається на окремій строку і містить наступні поля, розділені пробілами: вершина-джерело, вершина-призначення, a_S та b_S.
Вихідні дані
Вихід міститиме одну строку для кожного тестового вводу, що вказує мінімальний час для будь-якого автомобіля, щоб проїхати в мережі, округлений вниз до найближчого цілого числа.
Примітка: Перший ввід складається з 4 вершин і 4 ребер; 4000 автомобілів повинні проїхати від вершини 0 до вершини 3. Щоб досягти найменшого часу подорожі, автомобілі оберуть один з двох можливих шляхів (0-1-3) і (0-2-3) так, щоб кількість автомобілів на обох була рівною; отже, мінімальний час подорожі дорівнює нижчий (0.01 * 2000 + 45.1) = 65.
Другий ввід подібний до першого, за винятком ребра з нульовою вартістю, яке додано між вершинами 1 і 2. У цьому випадку всі автомобілі егоїстично обирають шлях (0-1-2-3) і мінімальний час подорожі дорівнює 80.