0

I have implemented dijkstra's code using a priority_queue in c++ and tried to submit this code here.

Here is my code:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pc(x) putchar(x)
#define gc() getchar()

inline void writeInt(int n)
{
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0)
    {
        pc('0');
        pc('\n');
        return;
    }
    while ((rev % 10) == 0)
    {
        count++;
        rev /= 10;
    }
    rev = 0;
    while (N != 0)
    {
        rev = (rev << 3) + (rev << 1) + N % 10;
        N /= 10;
    }
    while (rev != 0)
    {
        pc(rev % 10 + '0');
        rev /= 10;
    }
    while (count--)
        pc('0');
    pc(' ');
}

inline int FAST_IO()
{
    char ch;
    int val = 0;
    ch = gc();
    while (ch == '\n' || ch == ' ')
        ch = gc();
    val = 0;
    while (ch >= '0' && ch <= '9')
    {
        val = (val * 10) + (ch - '0');
        ch = gc();
    }
    return val;
}

int n, m;

void print(const vector<int> &parent, int n)
{
    if (n == -1)
        return;
    print(parent, parent[n]);
    writeInt(n);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    n = FAST_IO();
    m = FAST_IO();
    vector<vector<pair<int, ll>>> adj(n + 1);
    vector<int> parent(n + 1, -1);
    vector<ll> dist(n + 1, LLONG_MAX);
    vector<bool> processed(n + 1, false);

    while (m--)
    {
        int u = FAST_IO();
        int v = FAST_IO();
        int w = FAST_IO();
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    auto cmp = [&dist](const int &a, const int &b)
    {
        return dist[a] > dist[b];
    };

    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    pq.push(1);
    dist[1] = 0;
    while (!pq.empty())
    {
        int u = pq.top();
        pq.pop();
        if (u == n)
            break;
        if (processed[u])
            continue;
        processed[u] = true;

        for (auto &[v, w] : adj[u])
        {
            if (dist[u] + w < dist[v]) // if this is true then processed[v] should be false
            {
                //if v can be relaxed -> processed[v] is false

                dist[v] = dist[u] + w;
                parent[v] = u;

                if (processed[v]) // THIS CODE SHOULD NEVER RUN BUT IT DOES???
                    printf("%d is processed", v);

                // if (!processed[v])//redundant
                pq.push(v);
            }
        }
    }

    if (dist[n] < LLONG_MAX)
        print(parent, n);
    else
        printf("-1");

    return 0;
}

The issue occurs when I relax a node v. According to dijkstra's algorithm, we have found the min. distance to a node v if we have processed that node and are currently on it. So this is exactly what I do. Whenever I pop a node from the heap, this means that we have found the shortest distance to that node so I mark that node as processed[v] = true.

Now whenever I relax a node, this means that I found a distance to that node that is less than the distance previously computed (i.e. I found a shorter path). This implies that that node cannot have already been processed (i.e. processed[v] is false). So to test this, I wrote an if statement inside the relaxation portion which prints something if we find a node that we can relax and it has already been processed. According to the algorithm, this should never be possible and it is like writing:

if(false)//this will never run
    print(something);

But this fails in the codeforces submission because for some reason the if statement runs which is what I don't understand. I have even tried to make everything long long incase it was a overflow error but that also gives the same output.

Ak01
  • 194
  • 12
  • 1
    Just a note, but [here is why you should not include `bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Jakob Stark Apr 05 '22 at 08:48

0 Answers0