![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
![]()
Помогите с задачей - http://www.acmp.ru/index.asp?main=task&id_task=206
Меня смущает то, что вершина задается двумя величинами - номером станции и временем, причем время - до 10^9. Хотя бы например, как хранить кратчайшее расстояние для каждой вершины - array[100][1000000000]? Единственный способ, который я вижу - не разделять вершину на вершины по времени, а работать как с одной, но тогда вообще непонятно как искать кратчайший путь? |
![]() |
![]() |
![]() |
#2 |
Пользователь
Регистрация: 17.09.2009
Сообщений: 40
|
![]()
Здесь не нужны никакие графы, это динамическое программирование. Строите массив из N элементов. Далее цикл из M шагов. На каждом j-ом шаге i-ый элемент матрицы показывает минимальное время, за которое можно добраться до i-ой станции, пользуясь только первыми j электричками. Чтобы заполнить i-й элемент на j+1 шаге, надо пройтись по всему массиву, найти все станции, на которых останавливается M-ая электричка, и не просто останавливается, а не раньше, чем значение этого элемента (т.е минимальное время прибытия на эту станцию). Смотрим останавливается ли после этого электричка на i-ой станции. Если останавливается, то смотрим во сколько, и из всех таких возможных времен прибытия на i-ую станцию выбираем минимальное. Т.е по времени получается
100(шагов)*100(станций прибытия)*100(станций отъезда на предыдущим шаге)*100(станций для проверки останавливается ли электричка на i-ой станции)=10^8 Не очень хорошо. Я эту задачу давно делала, тогда была тестирующая система с тестами с олимпиады, последний тест не прошла по времени. Но, поскольку индексы станций в расписании для каждой электрички расположены в возрастающем/убывающем порядке, то поиск останавливается ли электричка на i-ой станции можно сделать за log_2 100=7 |
![]() |
![]() |
![]() |
#3 | |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
![]()
Спасибо конечно огромное, но мне все равно еще не все понятно:
Цитата:
|
|
![]() |
![]() |
![]() |
#4 | |
Пользователь
Регистрация: 17.09.2009
Сообщений: 40
|
![]()
Да, похоже я что-то не так написала, ведь по такому алгоритму у меня получается, что он не может j+1-ой электричкой воспользоваться раньше, чем j-ой. Но это точно динамическое программирование, как можно графы сюда впихнуть не знаю.
Нашла в инете такое решение Цитата:
Последний раз редактировалось Грымзик; 26.03.2010 в 20:11. |
|
![]() |
![]() |
![]() |
#5 |
Пользователь
Регистрация: 17.09.2009
Сообщений: 40
|
![]()
Я не представляю как это можно с помощью графов искать, ведь что можно считать весом дуги? Время проезда между станциями? Но ведь не оно важно, а именно время прибытия...
Последний раз редактировалось Грымзик; 26.03.2010 в 20:12. |
![]() |
![]() |
![]() |
#6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
![]()
Самое тупое решение - это Беллмен-Форд. А вообще можно обходом в ширину написать, если ограничения повыше.
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Графы | Prisian | Общие вопросы Delphi | 11 | 02.05.2013 22:02 |
Графы | Пaвeл | Помощь студентам | 0 | 14.03.2010 10:00 |
графы | delete | Общие вопросы C/C++ | 2 | 28.10.2009 21:31 |
Графы на С++ | corri | Общие вопросы C/C++ | 3 | 03.10.2009 01:42 |
графы | paladinn | Помощь студентам | 1 | 07.06.2009 18:04 |