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

Алгоритм Дейкстры - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти среднее арифметическое наибольшего и наименьшего значений элементов матрицы http://www.cyberforum.ru/cpp-beginners/thread884977.html
Данная действительно матрица размером 6 х 9. Найти среднее арифметическое наибольшего и наименьшего значений ее элементов.
C++ Найти среднее арифметическое наибольшего и наименьшего значений элементов матрицы Заполнить массив А с 6 строк и 9 столбцов по следующему правилу: Данная действительно матрица размером 6 х 9. Найти среднее арифметическое наибольшего и наименьшего значений ее элементов. http://www.cyberforum.ru/cpp-beginners/thread884976.html
C++ Удаление элемента из дерева
Нужно написать код для удаления элемента из дерева, почему-то всегда возвращает NULL в функциях Right и Left, и следовательно newnode->x не существует, помогите разобраться в чем дело Node *...
C++ Ход коня по шахматной доске случайным образом
Используйте генерацию случайного числа для предоставления коню возможности ходить по шахматной доске случайным образом (конечно, только допустимым Сам понимаю, что ужасно туплю сейчас, но все...
C++ Обработка записей (список учеников имеет следующую структуру: фамилия – номер школы – число баллов по ЕГЭ – оценка) http://www.cyberforum.ru/cpp-beginners/thread884939.html
Разработать и отладить программу обработки записей. Предусмотреть: - ввод данных - вывод результатов (на экран в виде таблицы и в файл) Задача: Список учеников имеет следующую структуру:...
C++ Прямые на плоскости(С++) Доброго времени суток господа. Помогите пожалуйста написать эту задачку в С++. Сам с этой задачей пока не разбирался, времени нету, а задач много :cry: (сам пока другими разбираюсь :pardon:) ... подробнее

Показать сообщение отдельно
Lvaruky
8 / 8 / 0
Регистрация: 10.05.2013
Сообщений: 26
16.06.2013, 15:16
http://e-maxx.ru/algo/dijkstra

далал как-то, только там ввод вывод через iostream, не претендую на самую хорошую оптимизацию, но все работает:
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
#include <iostream>
#include <vector>
#define INF 1000000000
 
using namespace std;
 
void main () {
    int N,M,v1,v2;
    cin>>N>>M>>v1>>v2;
    v1--;v2--;
    vector<vector<pair<int,int>>> G(N);
    int start,end,length;
    for (int i = 0; i < M; i++) {
        cin>>start>>end>>length;
        start--;end--;
        G[start].push_back(make_pair(end,length));
        G[end].push_back(make_pair(start,length));
    }
    vector<int> d(N,INF);
    vector<bool> used(N,false);
    d[v1]=0;
    for (int i=0; i<N; i++) {
        int v = -1;
        for (int j=0; j<N; j++)
            if (!used[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        used[v] = true;
        for (int j=0; j<G[v].size(); j++) {
            int to = G[v][j].first;
            if (d[to] > d[v]+G[v][j].second) {
                d[to]=d[v]+G[v][j].second;
            }
        }
    }
 
    if (d[v2] == INF) {
        cout<<-1;
    } else {
        cout<<d[v2];
    }
}
работает за O(n^2+m)
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru