Планировщик маршрутов
Ацикличная дорожная сеть состоит из однонаправленных дорожных сегментов (рёбер), каждое из которых соединяет два перекрёстка (вершины) из общего числа N перекрёстков. Время, необходимое для проезда по дорожному сегменту, всегда положительное и зависит линейно от количества автомобилей C, использующих сегмент s:
T(s) = a_SC + 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.