Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
#1

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

19.12.2010, 14:45. Просмотров 1893. Ответов 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)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2010, 14:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстры (цена на бензин) (C++):

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

Алгоритм Дейкстры С++ - C++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности. как можно после того как...

Алгоритм Дейкстры - C++
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные связи между вершинами заполнить их длинами,...

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

Алгоритм Дейкстры - C++
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include<iostream> #include<fstream> ...

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

Тут нужно учесть что пути в конечный город может и не быть совсем.
2
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,545
Завершенные тесты: 3
19.12.2010, 16:34 #7
valeriikozlov,
(она при самом плохом раскладе имеет размер N*N).
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
0
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);
       }
Цикл бесконечный получается..
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 16:45 #9
Цитата Сообщение от ForEveR Посмотреть сообщение
Э... Я чего-то недопонял, но насколько я помню дискретку - матрица смежности всегда имеет размер N*N, где N - кол-во вершин.
Я просто сравнивал размеры матрицы смежности и матрицы инцидентности.
Матрица смежности всегда
Цитата Сообщение от ForEveR Посмотреть сообщение
имеет размер N*N, где N - кол-во вершин.
А вот матрица инцидентности может быть и меньше ее размерами - при малом M
Цитата Сообщение от rustock Посмотреть сообщение
M – количество дорог в стране
а может быть и больше в несколько раз.
Плохой расклад это максимальное кол-во дорог.
2
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:47  [ТС] #10
Первый город 1. Последний город n.
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 16:48 #11
rustock, Ссылка есть где задачу можно сдать?
2
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 16:48  [ТС] #12
Цитата Сообщение от valeriikozlov Посмотреть сообщение
rustock, Ссылка есть где задачу можно сдать?
)
0
valeriikozlov
Эксперт С++
4673 / 2499 / 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);
       }
3
rustock
8 / 8 / 1
Регистрация: 29.11.2010
Сообщений: 154
19.12.2010, 17:32  [ТС] #14
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вот рабочий вариант:
Спасибо!! Вы меня просто выручили сегодня!!
Как увеличить репутацию?
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 17:33 #15
не знаю
2
19.12.2010, 17:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2010, 17:33
Привет! Вот еще темы с ответами:

Алгоритм Дейкстры - C++
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту задачу алгоритмом дейкстры. Вроде сам алгоритм правильно...

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

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

Алгоритм Дейкстры - C++
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на паскале, а именно вот этого кода const int INF = 1000000000; ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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