Входной файл: PER.IN Выходной файл: PER.OUT Время на тест: 5 секунд Тесты к задаче:Скачать
Даны декартовы координаты N перекрестков города, которые пронумерованы от 1
до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков
соединены дорогами с двухсторонним (правосторонним) движением, которые
пересекаются только на перекрестках. Для каждой дороги известно время, которое
требуется для проезда по ней от одного перекрестка до другого.
Необходимо проехать от перекрестка с номером А до перекрестка с номером В
за минимальное время.
Время проезда зависит от набора проезжаемых дорог и от времени ожидания на
перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по
дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на
перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы
поворачиваете налево, то время ожидания равно D*К, где D равно количеству
дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не
поворачиваете налево, то время ожидания равно нулю.
Написать программу, которая определяет самый быстрый маршрут.
Спецификация входных данных.
Входные данные находятся в текстовом файле с именем PER.IN и имеют
следующую структуру:
в первой строке находится число N (натуральное, <=1000);
во второй строке - количество дорог M (натуральное, <=1000);
в третьей строке - константа K (натуральное число, <=1000);
в каждой из N следующих стpок находится паpа чисел х и у, разделенных
пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по
модулю 1000);
в каждой из M следующих строк находится 3 числа p, r, t, разделенные
пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t
(натуральное, <=1000) - время проезда по ней;
в последней строке находятся номера начального А и конечного В
перекрестков.
Спецификация выходных данных.
Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и
иметь следующий формат:
в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;
в каждой из следующих строк находится одно число - номер очередного
перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).