Планувальник доріг#2567
Ациклічна дорожня мережа складається з односторонніх дорожніх сегментів (ребер), кожен з яких з'єднує два перехрестя (вершини) із загальної кількості перехресть. Час, необхідний для проходження відрізка дороги, завжди додатний і лінійно залежить від кількості машин , що користуються цим відрізком :
Тут a_S та b_S — це дві константи, задані у форматі чисел з плаваючою крапкою одинарної точності, які описують властивості дорожнього відрізка . Час перетину перехрестя дорівнює .
Певна кількість машин має проїхати від вершини до вершини N - 1 цією мережею доріг. Кожен водій обирає маршрут, керуючись власними інтересами, мінімізуючи свій час у дорозі, розуміючи, що й інші водії чинять так само. Необхідно написати програму, яка визначить, скільки автомобілів користується кожним із можливих маршрутів від початкової до кінцевої вершини, а також яким буде витрачений час для кожного з маршрутів.
Файл вхідних даних містить декілька тестів і організований наступним чином. У першому рядку зазначено кількість тестів. Далі йдуть описи тестів. Кожен тест починається з рядка, що містить кількість вершин, кількість ребер і кількість машин, розділених пробілами. Далі для кожного ребра подано окремий рядок з такими полями через пробіли: вершина-джерело, вершина-призначення, a_S і b_S.
Для кожного тесту виведіть один рядок з мінімальним часом, необхідним будь-якій машині, щоб проїхати мережею, округленим до меншого цілого.
Примітка: Перший вхідний тест містить вершини та ребра; машин повинні проїхати від вершини до вершини . Для досягнення мінімального часу руху, автомобілі розподіляються між двома можливими маршрутами (0-1-3) та (0-2-3) порівну; отже, мінімальний час у дорозі дорівнює \lfloor 0.01 \cdot 2000 + 45.1 \rfloor = 65.
Другий тест аналогічний першому, але додається ребро з нульовою вартістю від вершини до вершини . У такому випадку всі автомобілі, діючи у власних інтересах, обирають маршрут (0-1-2-3), і мінімальний час у дорозі дорівнює .
Приклад 1