|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1614. Таксист
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Имеется N городов, связанных M дорогами (нумерация дорог и городов начинается с 1). Движение по дорогам осуществляется только в одном направлении, при этом дороги пересекаются только в городах. Известна длина каждой дороги. Таксисту надо проехать из города с номером 1 из города с номером N таким образом, чтобы длина его маршрута отличалась не более, чем на величину K от длины минимального пути между этими городами. Необходимо найти все дороги, по которым может пройти маршрут таксиста. Входные данные Первая строка содержит числa N (2 ≤ N ≤ 104), M (1 ≤ M ≤ 3 × 104) и K (0 ≤ K ≤ 104). · Каждая из последующих M строк выходного файла содержит три числа: начальный город, конечный город и ее длина (длина каждой дороги положительна и не превосходит величины 104). Числа в строках целые и разделены одним или несколькими пробелами. Выходные данные Первая строка выходного файла должна содержать число l — количество дорог, которые таксист потенциально может использовать. Каждая из следующих l строк этого файла содержит одно число: номер потенциальной дороги (номера дорогам присваиваются в соответствии с тем, в какой последовательности они были введены) и дороги следуют в порядке возрастания. Пример Входные данные 4 5 1 Выходные данные 4
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Сборы в Перми 2009 / | 10.07.09 Большой контест / |
| 1613. G - Проезд с промежуточной остановкой | 1614. | 1615. I - Путешественник |
| время генерации 0.344 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |