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

Алгоритм Дейкстры (цена на бензин) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 14:45     Алгоритм Дейкстры (цена на бензин) #1
Думаю с этой задачей многие сталкивались

Входные данные
Во входном файле 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")
Сравнить цены всех маршрутов, и вывести меньшую цену..
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2010, 14:45     Алгоритм Дейкстры (цена на бензин)
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 15:27     Алгоритм Дейкстры (цена на бензин) #2
Сам алгоритм Дейкстры нормально объясняется например здесь:
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 15:35  [ТС]     Алгоритм Дейкстры (цена на бензин) #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сам алгоритм Дейкстры нормально объясняется например здесь:
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Это я уже видел, правда не знаю как это реализовать
Поэтому попросил псевдокод на си
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
19.12.2010, 15:53     Алгоритм Дейкстры (цена на бензин) #4
rustock, Псевдокод на си это что-то новенькое)
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 15:56  [ТС]     Алгоритм Дейкстры (цена на бензин) #5
Цитата Сообщение от ForEveR Посмотреть сообщение
rustock, Псевдокод на си это что-то новенькое)
Тьфу оговорился.. Думаю вы меня поняли)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 16:08     Алгоритм Дейкстры (цена на бензин) #6
Тогда давайте так:
Создаем один массив для хранения цен на бензин: 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.

Тут нужно учесть что пути в конечный город может и не быть совсем.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
19.12.2010, 16:34     Алгоритм Дейкстры (цена на бензин) #7
valeriikozlov,
(она при самом плохом раскладе имеет размер N*N).
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:42  [ТС]     Алгоритм Дейкстры (цена на бензин) #8
Так чтоли?:
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);
       }
Цикл бесконечный получается..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 16:45     Алгоритм Дейкстры (цена на бензин) #9
Цитата Сообщение от ForEveR Посмотреть сообщение
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
Я просто сравнивал размеры матрицы смежности и матрицы инцидентности.
Матрица смежности всегда
Цитата Сообщение от ForEveR Посмотреть сообщение
имеет размер N*N, где N - кол-во вершин.
А вот матрица инцидентности может быть и меньше ее размерами - при малом M
Цитата Сообщение от rustock Посмотреть сообщение
M – количество дорог в стране
а может быть и больше в несколько раз.
Плохой расклад это максимальное кол-во дорог.
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:47  [ТС]     Алгоритм Дейкстры (цена на бензин) #10
Первый город 1. Последний город n.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 16:48     Алгоритм Дейкстры (цена на бензин) #11
rustock, Ссылка есть где задачу можно сдать?
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:48  [ТС]     Алгоритм Дейкстры (цена на бензин) #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
rustock, Ссылка есть где задачу можно сдать?
http://********/index.asp?main=task&id_task=133 )
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 17:25     Алгоритм Дейкстры (цена на бензин) #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот рабочий вариант:
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);
       }
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 17:32  [ТС]     Алгоритм Дейкстры (цена на бензин) #14
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вот рабочий вариант:
Спасибо!! Вы меня просто выручили сегодня!!
Как увеличить репутацию?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 17:33     Алгоритм Дейкстры (цена на бензин) #15
не знаю
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2010, 17:35     Алгоритм Дейкстры (цена на бензин)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 17:35  [ТС]     Алгоритм Дейкстры (цена на бензин) #16
Дайте ему "+++++" к репутации
Yandex
Объявления
19.12.2010, 17:35     Алгоритм Дейкстры (цена на бензин)
Ответ Создать тему
Опции темы

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