|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
Алгоритм Дейкстры (цена на бензин)19.12.2010, 14:45. Показов 3194. Ответов 15
Метки нет (Все метки)
Думаю с этой задачей многие сталкивались
![]() Входные данные Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Далее идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя. Выходные данные В выходной файл OUTPUT.TXT выведите одно число – суммарную стоимость маршрута или -1, если добраться невозможно. Пример входного файла: 4 1 10 2 15 4 1 2 1 3 4 2 4 3 Пример выходного файла: 3 Пожалуйста помогите с кодом, или хотя бы объясните сам алгоритм Дейкстры (на си) ![]() Добавлено через 16 минут Как я понял: Условие: Если можно из первого города попасть в последний (в нашем случае из 1 в 4), то найти все возможные маршруты (в нашем случае 1>3>4 или 1>2>4), иначе (вывести "-1") Сравнить цены всех маршрутов, и вывести меньшую цену..
0
|
|
| 19.12.2010, 14:45 | |
|
Ответы с готовыми решениями:
15
Цена на бензин каждую весну повышается на x%, а каждую осень опускается на y%. На сколько процентов изменится цена литра бензина через z лет? Цена на бензин!!?? Алгоритм Дейкстры |
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 19.12.2010, 15:27 | |
|
Сам алгоритм Дейкстры нормально объясняется например здесь:
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
2
|
|
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
||
| 19.12.2010, 15:35 [ТС] | ||
![]() Поэтому попросил псевдокод на си
0
|
||
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
| 19.12.2010, 15:53 | |
|
rustock, Псевдокод на си это что-то новенькое)
0
|
|
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
| 19.12.2010, 15:56 [ТС] | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 19.12.2010, 16:08 | |
|
Тогда давайте так:
Создаем один массив для хранения цен на бензин: mas_benz[N]. В него считываем цены на бензин для каждого города. Создаем или матрицу смежности или матрицу инцидентности для хранения данных от том какие города связаны. Я бы создал матрицу смежности (она при самом плохом раскладе имеет размер N*N). Например матрицу mas[N][N]. Туда считываем данные о том какие года связаны. Затем создаем массив для хранения минимального значения пути. Например mas_res[N]. Заполняем его значениями 10000. Это так сказать бесконечность. И создаем массив для контроля что город прошли (так сказать для вычеркивания города) например int mas_kontr[N]={0}. Затем сам алгоритм Дейкстры: (Кстати я не увидел в задании: начальный и конечный город задаются, или начальный всегда первый, а конечный город всегда последний? Ну да ладно) Заводим переменную int temp (в которой будем хранить номер очередного проверяемого города, который после проверки вычеркнем). 1. Например начальный город имеет номер X. Тогда temp=X-1. mas_res[X-1]=0. 2. Находим все остальные города связанные с этим городом (и у которых mas_kontr[i]==0) и для них проверяем для них if(mas_res[temp]+mas_benz[temp]<mas_res[i]) mas_res[i]=mas_res[temp]+mas_benz[temp]; 3. mas_kontr[temp]=1; 4. Ищем новый temp по принципу: temp будет равно (номер города -1) для которого mas_res[номер города -1] минимально и mas_kontr[номер города -1] равно 0. И идем к п.2. Тут нужно учесть что пути в конечный город может и не быть совсем.
2
|
|
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||
| 19.12.2010, 16:34 | ||
|
valeriikozlov,
0
|
||
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
||||||
| 19.12.2010, 16:42 [ТС] | ||||||
|
Так чтоли?:
0
|
||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||
| 19.12.2010, 16:45 | ||||
|
Матрица смежности всегда Плохой расклад это максимальное кол-во дорог.
2
|
||||
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
| 19.12.2010, 16:47 [ТС] | |
|
Первый город 1. Последний город n.
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 19.12.2010, 16:48 | |
|
rustock, Ссылка есть где задачу можно сдать?
2
|
|
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
| 19.12.2010, 16:48 [ТС] | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 19.12.2010, 17:25 | ||||||
Сообщение было отмечено как решение
Решение
Вот рабочий вариант:
3
|
||||||
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
| 19.12.2010, 17:32 [ТС] | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 19.12.2010, 17:33 | |
|
не знаю
2
|
|
|
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
|
|
| 19.12.2010, 17:35 [ТС] | |
|
Дайте ему "+++++" к репутации
0
|
|
| 19.12.2010, 17:35 | |
|
Помогаю со студенческими работами здесь
16
Алгоритм Дейкстры Алгоритм Дейкстры Алгоритм Дейкстры Алгоритм Дейкстры Алгоритм Дейкстры Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет
значение производной при заданном х
Логарифм записывается как: (x-2)log(x^2+2) -. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|