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

Работа с графами. Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти ошибку в коде http://www.cyberforum.ru/cpp-beginners/thread830139.html
Программа не выходит из данного цикла(например, если массив comp из чисел 1 1 5 5 5, то все равно пишет KARE) for(int a=0, b=1, c=2, d=3; c<5; d++) { if(d==a||d==b||d==c) continue; if(comp==comp&&comp==comp&&comp==comp) { cout<<"KARE"; intel=intel=intel=intel=false; kare=true; break;
C++ Вывести на экран символ ASCII таблицы заданное количество раз Всем привет. надо вывести на экран символ аски таблицы такое кол во раз, какое значение хранится в поле структуры. чето меня переклинило. ну или просто как вывести символ на экран указанное кол во раз.void myClass::show() { int l=219; ptek=pbeg; while(ptek->next) { cout<<ptek->a<<" "<<ptek->b<<endl; ptek=ptek->next; } http://www.cyberforum.ru/cpp-beginners/thread830108.html
Как написать плеер для Windows ? C++
Посоветуйте какие-то книги стати советы. Правильно ли я понимаю что: - с помощью кодеков декодируется видео и аудио, но что они выдают на выход? - и что такое сами кодеки? это COM-объекты? или что это и как с ними взаимодействовать в программе? - чем, после декодирования, видео и аудио рендертися на экран с помощю DirectX или ещё чего-то? Если можно перечислите какие минимальные знания...
Переменная базового класса в производных классах C++
Есть абстрактный базовый класс и в нем определена переменная variable: class Base { public: int variable; }; И есть два производных класса, которые используют переменную базового класса variable:
C++ Конструкторы http://www.cyberforum.ru/cpp-beginners/thread830076.html
Пытаюсь разработайте класс представления окна на экране компьютера. В состав должны войти следующие конструкторы: -конструктор по умолчанию; -конструктор с параметрами; -копирующий конструктор. #include <iostream.h> #include <conio.h> #include <stdio.h> class my {int x1,x2,y1,y2,col; public:
C++ «Моделирование процессов преобразования информации в сопроцессоре» Необходимо реализовать программу, выполняющую конверсию введенного с клавиатуры десятичного числа с плавающей точкой в формат сопроцессора и обратное преобразование (вводится двоичное представление, программа выдает соответствующее десятичное число). Ввод осуществляется с клавиатуры, вывод на экран. Программа должна поддерживать все три типа данных сопроцессора. подробнее

Показать сообщение отдельно
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.04.2013, 15:03     Работа с графами. Алгоритм Дейкстры
Для произвольного графа:
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
#include <iostream>
#include <cmath>
#include <vector>
#include <limits>
#include <algorithm>
 
using namespace std;
 
#define mp make_pair
 
int main(){         
    int n, m, v1, v2;
    cin >> n >> m >> v1 >> v2;
    v1--; v2--;
    vector<vector <pair<int, int>>> g(n);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;b--;
        g[a].push_back(mp(b, w));
        g[b].push_back(mp(a, w));
    }
    int INF = INT_MAX - 1e3;
    vector <int> d(n, INF);
    vector <bool> used(n, false);
    d[v1] = 0;
    int u = 0;
    while (u != -1){
        u = -1;
        int mx = INF;
        for (int i = 0; i < n; i++){
            if (!used[i] && d[i] < mx){
                mx = d[i];
                u = i;
            }
        }
        if (u != -1){
            for (int i = 0; i < g[u].size(); i++){
                int to = g[u][i].first;
                int w = g[u][i].second;
                if (!used[to] && d[u] + w < d[to]){
                    d[to] = d[u] + w;
                }
            }
            used[u] = 1;
        }
    }
    cout << ((d[v2] == INF)?-1:d[v2]);
    return 0;
}
Вот для разряженного за M Log N
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
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <tuple>
 
using namespace std;
 
#define mp make_pair
 
int main(){         
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector <pair<int, int>>> g(n);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;b--;
        g[a].push_back(mp(b, w));
        g[b].push_back(mp(a, w));
    }
    int INF = INT_MAX - 1e3;
    vector <int> d(n, INF), p(n, -1);
    vector <bool> used(n, false);
    set <pair<int, int>> mn; 
    d[0] = 0;
    mn.insert(mp(0, 0));
 
    while (!mn.empty()){
        int u = (*mn.begin()).second;
        mn.erase(mn.begin());
        for (int i = 0; i < g[u].size(); i++){
            int to = g[u][i].first;
            int w = g[u][i].second;
            if (!used[to] && d[u] + w < d[to]){
                d[to] = d[u] + w;
                p[to] = u;
                mn.insert(mp(d[to], to));
            }
        }
    }
    if (d[n-1] == INF){
        cout << "No solution";
    }else{
        stack <int> st;
        int t = n-1;
        while (t != 0){
            st.push(t+1);
            t = p[t];
        }
        printf("%d ", 1);
        while (!st.empty()){
            printf("%d ", st.top());
            st.pop();
        }
    }
    return 0;
}
 
Текущее время: 13:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru