When we use a priority_queue for dijkstra, it reduces the complexity to O(E*logV) but it guarentees us that when we pop a node from the heap, we have found the shortest distance to that node. So, whenever I pop a node from the heap, I set processed[node] = true. Then, when I relax any of its neighbors, I don't check if they are processed because I know that if a node can be relaxed, i.e. we found a distance that is smaller than the prev dist computed for it, then that means the node cannot have been processed.
Just to double check, I put a if statement that prints something if processed[v] is true (which, as I said above, should never happen) inside the portion of the code that relaxes node v. However, this fails in some Codeforces test cases because the if statement prints which I don't understand why. I ran this code on https://mirror.codeforces.com/problemset/problem/20/C
#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?
{
//v can be relaxed -> processed[v] is false
if (processed[v]) // THIS CODE SHOULD NEVER RUN BUT IT DOES??
cout << "dv = " << dist[v] << "\tdu + w = " << (dist[u] + w) << '\n';
dist[v] = dist[u] + w;
parent[v] = u;
// if (!processed[v])//redundant
pq.push(v);
}
}
}
if (dist[n] < LLONG_MAX)
print(parent, n);
else
printf("-1");
return 0;
}