Как исправить алгоритм Дейкстры?

Question

[impelix]

Написал алгоритм дейкстры, но он не работает. Про время знаю что не самый быстрый, но это пока не важно.
Входные данные: размер и сама матрица смежности и точка старта и точка до которой надо вывести расстояние от точки старта. Сам алгоритм ниже.
Не пойму почему выводит инт макс, пробовал отдебажить не получилось

Код

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);

void relax(int i, int j, int h){
    if (dist[i] + h < dist[j])
        dist[j] = dist[i] + h;
    }

int main() {
    int n, s, f, v, min;
    cin >> n >> s >> s;
    --s;
    --f;
    int g[n][n], used[n], dist[n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[j][i];
        }
    }
    used.resize(n);
    dist.resize(n);
    dist[s] = 0;
    for(int i = 1; i < n; i++)
    {
        min = INT_MAX;
        v = -1;
        for(int j = 1; j <= n; j++)
            if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}
        if (v < 0) break;
        for( int j = 1; j <= n; j++)
            if (used[j] == 0 && g[v][j] != -1)
                relax(v,j,g[v][j]);
        used[v] = 1;
    }
    if (dist[f] == INT_MAX) {
        cout << "-1";
        return 0;
    }
    cout << dist[f];
}

Пример
Ввод:
3 2 1
0 1 1
4 0 1
2 1 0
Вывод:
3
Также надо сделать восстановление пути, но благодаря бфсу я уже этому научился :)

Comments

[mayton2019]

Вот любишь ты писать в олимпиадном стиле. Все одной простыней. И разбивать на мини-функции тоже не любишь.
И что expected и что actual тоже не указываешь. И любишь заставлять бедных С++ ников дико напрягать мозг чтоб
скомпилировать это в уме.

[impelix]

mayton2019, ну олимпиадки пока выглядят интересно, если есть вопросы можешь задать или попробовать скомпилить это в каком-нибудь онлайн компиляторе(в этом есть небольшой плюс олимпиадных кодов)

[Wataru]

Этот код не компилируется же:

int g[n][n], used[n], dist[n];
used.resize(n);
dist.resize(n);

Вы с массивами работаете как с векторами.

Еще косяки:
часть циклов от 0 до n-1, часть от 1 до n.
cin >> n >> s >> s; - явно хотели прочитать f, а не s два раза.

[Модератор]

Вы постоянно неправильно именуете свои вопросы. П.3.6 Регламента явно указывает, как это надо делать.
Когда вы регистрировались, вы обещали выполнять Регламент. Если вы будете продолжать нарушать Регламент, ваши вопросы могут быть удалены, а аккаунт заблокирован модераторами временно или навсегда.
Будьте благоразумны.

[impelix]

Wataru, и все равно не работает

код

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);

void relax(int i, int j, int h){
    if (dist[i] + h < dist[j])
        dist[j] = dist[i] + h;
    }

int main() {
    int n, s, f, v, min;
    cin >> n >> s >> f;
    //--s;
    //--f;
    int g[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }
    used.resize(n);
    dist.resize(n);
    dist[s] = 0;
    for(int i = 1; i < n; i++)
    {
        min = INT_MAX;
        v = -1;
        for(int j = 0; j < n; j++)
            if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}
        if (v < 0) break;
        for( int j = 0; j < n; j++)
            if (used[j] == 0 && g[v][j] != -1)
                relax(v,j,g[v][j]);
        used[v] = 1;
    }
    if (dist[f] == INT_MAX) {
        cout << "-1";
        return 0;
    }
    cout << dist[f];
}

[impelix]

impelix, теперь только выводит 1

[impelix]

чуть чуть дорписал заходит на 8 тестов из 12, в чем может быть проблема?

code

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);

void relax(int i, int j, int h){
    if (dist[i] + h < dist[j])
        dist[j] = dist[i] + h;
    }

int main() {
    int n, s, f, v, min;
    cin >> n >> s >> f;
    --s;
    --f;
    int g[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }
    used.resize(n);
    dist.resize(n);
    dist[s] = 0;
    for(int i = 1; i < n; i++)
    {
        min = INT_MAX;
        v = -1;
        for(int j = 0; j < n; j++)
            if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}
        if (v < 0) break;
        for( int j = 0; j < n; j++)
            if (used[j] == 0 && g[v][j] != -1)
                relax(v,j,g[v][j]);
        used[v] = 1;
    }
    if (dist[f] == INT_MAX) {
        cout << "-1";
        return 0;
    }
    cout << dist[f];
}

[Wataru]

impelix, Основной цикл надо гнать от 0 до n-1, а не от 1. Вы же в цикле одну вершину находите. Надо найти все n.

Еще у вас вектор dist инициализирован частично INT_MAX, частично 0.

[impelix]

Wataru, спасибо, зашли все 12 тестов

Answer 1

[Wataru]

Раз уж я в комментариях все разобрал, скопирую в ответ: куча мелких ошибок в коде, вроде:
- циклы с 1 вместо 0
- не инициализированные массивы
- опечатки

Comments

[mayton2019]

Не могу проголосовать ответом потому что в тексте не звучит ответ. Звучит просто набор рекомендаций. Я думаю что лучше все таки приаттачить сорцы и тогда можно и голосовать.

[Wataru]

mayton2019, Так автор уже отметил решением. А конкретные исправления в комментариях к вопросу. Там несколько итераций даже.

[mayton2019]

Wataru, ну ОК