Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Dimka Nikolaev
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 5
#1

Программа, вычисляющая по данному расписанию движения электричек минимальное время, когда ребята могут оказаться дома - C++

17.10.2012, 21:19. Просмотров 749. Ответов 2
Метки нет (Все метки)

Задача A Домой на электричках
Имя входного файла: a.in
Имя выходного файла: a.out
Максимальное время работы на одном тесте: 3 секунды
Максимальный объем используемой памяти: 8 мегабайт
Студенты возвращаются домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где учатся студенты, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
Формат входных данных
Во входном файле записаны сначала числа N (2 <= N <= 100) и E (2 <= E <= N). Затем записано число M (0 <= M <= 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 <= Ki <= N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 10^9). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
Формат выходных данных
В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
Пример
a.in
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
a.out
20
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2012, 21:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Программа, вычисляющая по данному расписанию движения электричек минимальное время, когда ребята могут оказаться дома (C++):

Могут ли два идущих подряд билета оказаться несчастливыми? - Visual Basic .NET
Назовем автобусный билет несчастливым, если сумма цифр его шестизначного номера делится на 13. Могут ли два идущих подряд билета оказаться...

Сколькими способами среди взятых карт могут оказаться 4 карты червовой масти? - Комбинаторика
Добрый день! Пожалуйста помогите решить задачу, уже весь мозг продумала. Соответствующие темы тоже посмотрела, но не получилось решить. ...

Подсчитайте, сколькими способами робот может оказаться в яме во время эксперимента - Turbo Pascal
1.Задача Walk. В начале эксперимента Робот стоит спиной к глубокой ямы на самом краю. Робот может делать один шаг каждую секунду или...

Программа, обрабатывающая расписание электричек - Turbo Pascal
Здраствуйте! Помогите пожалуйста с программой, никак не могу понять, как её написать с использованием записей. Вот сама формулировка:...

.NET 4.x Когда закидую в поток функцию время программа аварийно закрывается - C#
Вот такая ошибка когда нажимаю запустить программу Программа меняет обои рабочего стола по времени который задает пользователь(в сек.),...

Во сколько раз время движения лодки против течения больше времени движения по течению? - Механика
моторная лодка плывёт по реке

2
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,198
Завершенные тесты: 1
18.10.2012, 13:15 #2
Думаю, надо создать массив со всеми остановками всех маршрутов, отсортировать его по времени и пройти по нему последовательно. Таким образом, когда дойдём до некоторой остановки в какой-то момент времени, если уже удалось добраться до предыдущей остановки этого маршрута, то надо сохранить время текущей остановки.
0
Dimka Nikolaev
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 5
20.10.2012, 19:32  [ТС] #3
А не мог ли ты мне дать основу, а то я не бум-бум в программировании)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2012, 19:32
Привет! Вот еще темы с ответами:

За последнюю секунду равноускоренного движения автомобиль прошёл половину пути. Определите полное время движения. - Механика
За последнюю секунду равноускоренного движения автомобиль прошёл половину пути. Определите полное время движения. Незнаю даже и с чего...

За пиратскую Windows дома могут дать 2 года тюрьмы - Windows
Житель Екатеринбурга, установивший на свой домашний компьютер нелицензионные копии Microsoft Windows и Microsoft Office, предстанет перед...

Определить, сколькими способами ребята могут разделить грибы между собой - Pascal ABC
(сочетания с повторениями) Четверо ребят собрали в лесу 30 белых грибов. Сколькими способами они могут разделить их между собой?

Создаем систему детектора движения дома - КИП, датчики
Помогите с программой.Необходимо создать систему контроля движения.Более формально - необходимо контролировать территорию с помощью веб...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru