Есть ли какая-либо ошибка в реализации алгоритма dijkstra?

Question

Я только что изучил алгоритм Дейкстры и решил несколько проблем, и я пытаюсь решить эту проблему http://codeforces.com/problemset/problem/20/C, но я получаю неправильный ответ в тестовом примере 31. Я не мог понять, почему он получает неправильный ответ , Сначала он давал превышение лимита памяти в тестовом примере 31. Но когда я изменяю int на long long из d [], массив получает неправильный ответ. Пожалуйста, дайте мне знать, почему он получает неправильный ответ.

Мой код:

#include <bits/stdc++.h>

using namespace std;

typedef struct data Data;

struct data{
    long long int city,dis;
    bool operator < (const data & p) const{
        return dis > p.dis;
    }
};

#define tr(niloy,it) for(auto it = niloy.rbegin(); it != niloy.rend(); it++)

void dijkstra(const vector <long long int>  edge[],const vector <long long int>  cost[], int source, int destination,int n,int m)
{
    long long int d[n];
    bool nodes[n];
    vector <int> parent(n,-1);
    for(int i = 0; i < n; i++){
        d[i] = INT_MAX;
        parent[i] = -1;
        nodes[i] = false;
    }
    priority_queue <Data> p;
    Data u,v;
    u.city = 0;
    u.dis = 0;
    p.push(u);
    d[source] = 0;
    while(!p.empty()){
        u = p.top();
        p.pop();
        long long int ucost = d[u.city];
        if(u.city == destination)break;
        if(nodes[u.city])continue;
        nodes[u.city] = true;
        //cout << edge[u.city].size() << endl;
        for(int i = 0; i < edge[u.city].size(); i++){
            v.dis = ucost + cost[u.city][i];
            v.city = edge[u.city][i];
            if(d[v.city] > v.dis){
                ///cout << v.city << " " << u.city << endl;
                parent[v.city] = u.city;
                d[v.city] = v.dis;
                p.push(v);
            }
        }
    }
    vector<int> niloy;
    ///cout << d[destination] << endl;
    if(parent[destination] != -1){
        niloy.push_back(n);
        while(destination != 0){
            niloy.push_back(parent[destination]+1);
            destination = parent[destination];
        }
        tr(niloy,it)cout << *it << " " ;
    }else{
        ///cout << d[destination] << endl;
        cout << -1 << endl;
    }

}

int main()
{
    int n,m;
    cin>> n >> m;
    vector <long long int> edge[n],cost[n];

    int a,b,c;

    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        if(a == b)continue;
        edge[a-1].push_back(b-1);
        cost[a-1].push_back(c);
        edge[b-1].push_back(a-1);
        cost[b-1].push_back(c);
    }
    //cout << edge[0][0] << endl;
    dijkstra(edge,cost,0,n-1,n,m);

    return 0;
}

Answer 1

Реализация алгоритма выглядит правильно для меня, единственное, что кажется неправильным, это строка:

d[i] = INT_MAX;

INT_MAX будет 2 ^ 32 (почти 10 ^ 9), если компилятор использует 32-битные числа, в то время как максимально возможная действительная длина оптимального решения может быть больше, чем если бы у вас был линейный граф, такой как: 1 -> 2 -> 3 -> ... -> n и длина каждого ребра равна 10 ^ 6. В этом случае кратчайший путь будет почти 10 ^ 11, что больше, чем INT_MAX , что означает, что начальные значения для массива d на самом деле не являются "бесконечными", как того требует алгоритм Дейкстры.

Изменение начального значения на большее число должно решить эту проблему (10 ^ 12 должно быть достаточно, но вы также можете использовать LLONG_MAX ):

d[i] = 1000000000000; // 10^12