Форум программистов, компьютерный форум 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 * Left(Node *MDer) { if (MDer == NULL) return NULL; if (MDer->l!=NULL) { return Left(MDer->l); } else return MDer; }
C++ Ход коня по шахматной доске случайным образом
Используйте генерацию случайного числа для предоставления коню возможности ходить по шахматной доске случайным образом (конечно, только допустимым Сам понимаю, что ужасно туплю сейчас, но все же я только учусь. Вопрос находится в заголовке. Суть проблемы: понимаю как сделать, но не могу реализовать в программу. #include <iostream> #include <iomanip> #include <ctime>
C++ Обработка записей (список учеников имеет следующую структуру: фамилия – номер школы – число баллов по ЕГЭ – оценка) http://www.cyberforum.ru/cpp-beginners/thread884939.html
Разработать и отладить программу обработки записей. Предусмотреть: - ввод данных - вывод результатов (на экран в виде таблицы и в файл) Задача: Список учеников имеет следующую структуру: фамилия – номер школы – число баллов по ЕГЭ (от 0 до 100) – оценка. При вводе числа баллов рассчитайте оценку (до 40 баллов – «2», 40-59 баллов – «3», 60-89 баллов – «4», 90-100 баллов – «5») и...
C++ Прямые на плоскости(С++) Доброго времени суток господа. Помогите пожалуйста написать эту задачку в С++. Сам с этой задачей пока не разбирался, времени нету, а задач много :cry: (сам пока другими разбираюсь :pardon:) Прямая на плоскости может быть задано уравнением ax+by+c=0, где a и b одновременно не равны нулю. Будем рассматривать прямые только с целыми коэффициентами a,b,c.Пусть даны коэффициенты нескольких прямых:... подробнее

Показать сообщение отдельно
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 61
16.06.2013, 15:06  [ТС]     Алгоритм Дейкстры
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# include <fstream>
# include <iostream>
# include <algorithm>
# include <deque>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
struct item
{
    int conect;
    bool visit;
    int length;
    int time;
    item ()
    {
        conect = 0; visit = true; length = 0;
    }
};
int main ()
{
    int n, m, q, t, a, b, s, f;
    deque<int> d;
    fin>>n>>m;
    item** mas = new item*[n+1];
    for (int i = 0; i < n+1; i++)
        mas[i] = new item [n+1];//в доп. столбце хранится время преодоления перекрестка под номером строки
    for (int i = 0; i < m; i++)
    {
        fin >>a>>b>>t;
        mas[a][b].time = t;
        mas[a][b].conect = 1;
        mas[b][a].time = t;
        mas[b][a].conect = 1;
    }
    fin>>s>>f>>q;
    for(int i = 1; i<=n; i++)
    {
        int k = 0;
        for(int j =1; j<=n; j++)
            k += mas[i][j].conect;
        mas[i][0].conect=k*q;
    }
    for(int i = 1; i <= n; i++)
        mas[s][i].length = mas[s][0].conect;
    for (int i = 0; i < n+1; i++)
        mas[0][i].conect = -1;
    d.push_back(s);
    mas[0][s].conect = 0;//mas[s][0].conect;
    //int x=0;
    int * smas = new int[15];
    while(!d.empty())
    {
        s = *d.begin();
        d.pop_front();
        for (int i = 0; i < 15; i++)
            smas[i] = 99999;
        int c = 0;
        for (int i = 1; i < n+1; i++)
            if(mas[s][i].conect == 1 && mas[s][i].visit)
            {
                smas[c]=i;
                c++;
            }
        for (int i = 0; i < c-1; i++)
            for (int j = 1; j < c; j++)
                if(mas[s][smas[j]].time < mas[s][smas[i]].time)
                {
                    int buf = smas[i];
                    smas[i] = smas[j];
                    smas[j] = buf;
                }
        for(int i = 0; i < c; i++)
            d.push_back(smas[i]);
        for (int i = 0; i < c; i++)
        {
            if(mas[0][smas[i]].conect == -1 || mas[s][0].conect + mas[0][s].conect + mas[s][smas[i]].time < mas[0][smas[i]].conect)
            {
                mas[0][smas[i]].conect = mas[s][0].conect + mas[0][s].conect + mas[s][smas[i]].time;
                for (int j = 1; j < n+1; j++)
                    mas[smas[i]][j].length = mas[0][smas[i]].conect;
            }
        }
        for (int i = 0; i < n+1; i++)
            mas[i][s].visit = false;
        }
    if(mas[0][f].conect==-1)
        fout<<"No";
    else
        fout<<"Yes\n"<<mas[0][f].conect;
    return 0;
}
Вроде написал,но есть 3 проблемы:
1) На одном из тестов ошибка памяти
2) Ошибка времени выполнения
3) Ошибка времени выполнения

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