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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ не могу понять что не так((((( http://www.cyberforum.ru/cpp-beginners/thread214583.html
привет всем! у меня проблемка возникла компиятор никак не проглатывает мой код #include <iostream> using namespace std; int main() { struct candybar { char name; float weight; };
C++ Сортировка пузырьком с++ Сортировка пузырьком, все работает, но помогите поменять ввод цифр в ручную на ввод цифр рандома (от -100 до +100). #include <iostream> using namespace std; // наш массив int array; // сортировка void*Sort(int col) { // временная переменная для хранения промежуточного результата int trash=0; http://www.cyberforum.ru/cpp-beginners/thread214582.html
Нужно написать программу в с++ ,массивы C++
Из целочисленного массива Х(N) записать в массив Y(к)все элементы превышающие среднее арифметическое всех элементов массива Х.Удалить в массивах все элементы являющиеся не простыми числами.В программе написать функции:формирование массива Y,определение среднего арифметического,удаления элемента. Если можно подробно опишите процесс удаления элемента... ...
НОК и НОД C++
Здоров Всем ! Вот условие : Определить функцию для нахождения наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) двух натуральных чисел. Определить НОК и НОД для n введенных нату-ральных чисел. Спс
C++ STL>>list<_Ty> http://www.cyberforum.ru/cpp-beginners/thread214560.html
Подскажите, пожалуйста. Я сейчас пытаюсь вникнуть в суть контейнеров, их свойства и функции. Так вот, создал я двун. список с помощью list, тип определил свой, например _Ty. Добавление происходит четко, всё хорошо. После добавления решил, что нужно организовать поиск того узла. Задействовал функцию find() из algorithm, сделал сл. образом list<_Ty> ob1; .... _Ty data(2,3); // какой-то там...
C++ Сортировка слиянием Всем доброго время суток, дана задача: Требуется упорядочить элементы некоторого массива целых чисел, который следует упорядочить по возрастанию: Файл MergeSort.h #ifndef __MERGE_SORT_H__ #define __MERGE_SORT_H__ // Включить печать отладочных сообщений. #define DEBUG_ECHO 1 подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
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.

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