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.