Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.87/15: Рейтинг темы: голосов - 15, средняя оценка - 4.87
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
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
19.12.2010, 14:45
Ответы с готовыми решениями:

Цена на бензин каждую весну повышается на x%, а каждую осень опускается на y%. На сколько процентов изменится цена литра бензина через z лет?
Помогите пожалуйста решить задачку. Зачет горит.... Цена на бензин каждую весну повышается на x%, а каждую осень опускается на y%. На...

Цена на бензин!!??
стало мне интересно, где сколько стоит бензин! у нас в Вологде 92 стоит 22-30! в инете читаю о том что в среднем цены повысили на 2.6-2.8...

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...#include <iostream> ...

15
Эксперт С++
 Аватар для valeriikozlov
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  [ТС]
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сам алгоритм Дейкстры нормально объясняется например здесь:
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Это я уже видел, правда не знаю как это реализовать
Поэтому попросил псевдокод на си
0
В астрале
Эксперт С++
 Аватар для ForEveR
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  [ТС]
Цитата Сообщение от ForEveR Посмотреть сообщение
rustock, Псевдокод на си это что-то новенькое)
Тьфу оговорился.. Думаю вы меня поняли)
0
Эксперт С++
 Аватар для valeriikozlov
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
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
19.12.2010, 16:34
valeriikozlov,
(она при самом плохом раскладе имеет размер N*N).
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
0
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:42  [ТС]
Так чтоли?:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
main(){
       FILE *in,*out;
       in=fopen("input.txt","r");
       out=fopen("output.txt","w");
       int i,n,m,j,x;
       int f=0;
       int mas[101][101];
       int mas_benz[101];
       int mas_res[1000];
       int mas_kontr[101]={0};
       int temp=0;
       x=1;
       fscanf(in,"%d",&n); // количество городов
       
       for(i=0;i<n;i++){
       fscanf(in,"%d",&mas_benz[i]); // стоимость бензина
       }
       fscanf(in,"%d",&m); // количество дорог
       
       for(i=0;i<m;i++){
       for(j=0;j<m;j++){
       fscanf(in,"%d",&mas[i][j]); // соединения
       }
       }
       for(temp=x-1,mas_res[x-1]=0;temp<n;x++){
                                               for(i=0;i<n;i++){
                                                                
       if(mas_kontr[i]==0 && mas_res[temp]+mas_benz[temp]<mas_res[i]){
       mas_res[i]=mas_res[temp]+mas_benz[temp];
       mas_kontr[temp]++;
       f=f+mas_benz[temp];
       }
       }
       }
       
       fprintf(out,"%d",f);
       fclose(in);
       fclose(out);
       }
Цикл бесконечный получается..
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
19.12.2010, 16:45
Цитата Сообщение от ForEveR Посмотреть сообщение
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
Я просто сравнивал размеры матрицы смежности и матрицы инцидентности.
Матрица смежности всегда
Цитата Сообщение от ForEveR Посмотреть сообщение
имеет размер N*N, где N - кол-во вершин.
А вот матрица инцидентности может быть и меньше ее размерами - при малом M
Цитата Сообщение от rustock Посмотреть сообщение
M – количество дорог в стране
а может быть и больше в несколько раз.
Плохой расклад это максимальное кол-во дорог.
2
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:47  [ТС]
Первый город 1. Последний город n.
0
Эксперт С++
 Аватар для valeriikozlov
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  [ТС]
Цитата Сообщение от valeriikozlov Посмотреть сообщение
rustock, Ссылка есть где задачу можно сдать?
http://acmp.ru/index.asp?main=task&id_task=133 )
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
19.12.2010, 17:25
Лучший ответ Сообщение было отмечено как решение

Решение

Вот рабочий вариант:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
main(){
       FILE *in,*out;
       in=fopen("input.txt","r");
       out=fopen("output.txt","w");
       int i,n,m,x, j;
       int f=-1;
       int mas[101][101];
       int mas_benz[101];
       int mas_res[101];
       int mas_kontr[101]={0};
       int temp=0;
       x=1;
       fscanf(in,"%d",&n); // количество городов
       
       for(i=0;i<n;i++){
       fscanf(in,"%d",&mas_benz[i]); // стоимость бензина
       mas_res[i]=10000;
       for(j=0; j<n; j++)
           mas[i][j]=0;
       }
       fscanf(in,"%d",&m); // количество дорог
       
       for(i=0;i<m;i++){
           int temp1, temp2;
           fscanf(in,"%d %d",&temp1, &temp2); // соединения
           mas[temp1-1][temp2-1]=mas[temp2-1][temp1-1]=1;  
       }
       int fl=1; mas_res[0]=0;
       while(fl)
       {
           fl=0; temp=-1;
           for(i=0; i<n; i++)
               if(mas_res[i]!=10000 && mas_kontr[i]==0)
               {
                   fl=1;
                   if(temp==-1)
                       temp=i;
                   else
                       if(mas_res[i]<mas_res[temp])
                           temp=i;
               }
            for(i=0; i<n; i++)
                if(mas[temp][i]==1 && mas_kontr[i]==0)
                {
                    if(mas_res[temp]+mas_benz[temp]<mas_res[i])
                        mas_res[i]=mas_res[temp]+mas_benz[temp];
                }
            mas_kontr[temp]=1;
       }
       if(mas_res[n-1]!=10000)
           f=mas_res[n-1];       
       fprintf(out,"%d",f);
       fclose(in);
       fclose(out);
       }
3
8 / 8 / 2
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 17:32  [ТС]
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вот рабочий вариант:
Спасибо!! Вы меня просто выручили сегодня!!
Как увеличить репутацию?
0
Эксперт С++
 Аватар для valeriikozlov
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.12.2010, 17:35
Помогаю со студенческими работами здесь

Алгоритм Дейкстры
День добрый! Есть игровое поле M*M. Количесво графов - N. Есть матрица смежности этого игрового поля. Получить элемент матрицы можно...

Алгоритм Дейкстры
Люди добрые, помогите! Курсовая работа на эту тему. Может кто-нибудь сталкивался.

Алгоритм Дейкстры
Нужно сделать визуализацию алгоритма Дейкстры, подскажите как это лучше сделать?

Алгоритм Дейкстры
Как на С++ в консольном приложении описать алгоритм Дейкстры?

Алгоритм Дейкстры
Всем привет Нужно написать Алгоритм Дейкстры, я написал консольную программу, а нужно с графическим интерфейсом, пользоваться формами...


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

Или воспользуйтесь поиском по форуму:
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, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru