|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
06.02.2016, 15:50 | #1 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Недочет программы
Здравствуйте. Нужна помощь, отредактировать, улучшить программу.
Даны города, дороги, которые их связывают и нужный город. Мы появляемся в первом городе, и должны достичь нужного города. Во входном файле : В первой строке три цифры n, m, k n - кол-во городов m - кол-во пар дорог k - нужный город вторая строка содержит n чисел - налоги в каждом городе. третья строка содержит m пар чисел - дороги, которые связывают города (например, m = 2, тогда в третьей строке будет 1 2 3 2, значит, есть дорога между 1 и 2 городом, и между 3 и 2) Нужно пройти самым дешевым путем к нужному городу Если нельзя добраться туда, то вывести -1. Код:
|
07.02.2016, 11:13 | #2 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Алгоритм Дейкстры.
|
07.02.2016, 19:27 | #3 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Нашел, изменил под свою программу:
Код:
|
07.02.2016, 20:32 | #4 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Алгоритм Дейкстры детерминированный и выполняется пропорционально V^2, где V - количество вершин (городов). Он не может зацикливаться в принципе.
Но раз зацикливается - приводите и исходные данные. А кроме того - пройдитесь пошаговым отладчиком. |
07.02.2016, 21:10 | #5 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Он у меня зацикливается, пока не выключу программу.
Например: 4 2 4 1 5 3 1 1 2 3 1 |
08.02.2016, 00:26 | #6 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Выбрасывайте этот код. Оставьте только ввод.
Задача похожа на ту, что решается алгоритмом Дейкстры, но всё же не она. Тут я погорячился. Решением будет модификация алгоритма Дейкстры, т.к. здесь стоимость не дороги, а посещения города. Результат - как в алгоритме Дейкстры - массив D[i] минимальной итоговой стоимости пути из 1 города в i, и массив P[i] массив предков для восстановления пути. В вашем коде не видно ни D ни P. Отсюда и невозможность решения - нет реализации алгоритма. У меня начинается рабочая неделя, поэтому уже не смогу ничем помочь. |
08.02.2016, 06:12 | #7 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Ну вот почему везде Дейкстра?
Для невзвешенного графа прекраснор работает bfs. А по коду ТС все же Дейкстра. А по условию ТС bfs. Кому верить? Последний раз редактировалось Poma][a; 08.02.2016 в 06:17. |
08.02.2016, 13:22 | #8 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Думаю, что нужен всё-таки Дейкстра, вернее вариация на тему. Т.к. получается что взвешенное прохождение через города, а не по дорогам. Чисто теоретически, возможен случай, когда пройти через 10 промежуточных городов дешевле чем через 1 промежуточный. Хотя, если есть прямой путь от 1 к k - то это сразу решение.
А чистый BFS в результате даст лишь невзвешенное отдаление от 1-го города. Тем более, что Дейкстра - это и есть развитие BFS. --------------------------------- А в коде ТС почему-то не разглядел Дейкстру... Особенно, потому, что ожидаемый результат - массив стоимостей путей и массив восстановления пути. Последний раз редактировалось FPaul; 08.02.2016 в 13:25. |
08.02.2016, 16:10 | #9 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Утром не увидел строчку с налогами. Каюсь. Грешен. Дейкстру в массы
У ТС вообще нечто. Если это Дейкстра. То он ужасен. Если Форд - то тем более Последний раз редактировалось Poma][a; 08.02.2016 в 16:15. |
09.02.2016, 00:22 | #10 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Изменил, сделал алгоритмом Дейкстры. Сделал так:
если есть дорога из второго города в третий, то есть 2 3, то вес её будет равен налогу третьего города, а вес с 3 2 - весу второго города. Программа почти полностью работает. однако что-то она еще не выполняет, пишет, что неверный ответ. Помогите найти ошибку: Код:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
C++ Динамическое программирование. Где недочет? | UaKot | Помощь студентам | 14 | 22.06.2013 21:22 |
программа с++(исправить небольшой недочет) | Timmon | Общие вопросы C/C++ | 3 | 20.10.2012 01:21 |
Недочет в задаче. Неполное решение | Yankeee | Помощь студентам | 0 | 21.03.2012 15:28 |
Доработка Java программы. Не могу найти недочет в программе. | ISV-777 | Общие вопросы по Java, Java SE, Kotlin | 2 | 04.11.2011 20:24 |
Нужно исправить интересный недочет | hex666 | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 14.03.2010 20:45 |