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;
}
I don't think you can write the comparator this way. If you update the value of
dist[v]
, the order of nodes which are already insidepq
prior to the update, will not automatically reorder themselves based on the new value ofdist[v]
.More detailed explanation here.
I added my code with assertions:
priority_queue
: 152769275set
: 152769530You can prove your solution will always get the correct answer. The heap not always provide the minimum, which is why you're reprocessing some nodes, but on most graphs it should be fast. Could you submit to https://cses.fi/problemset/task/1671 so that I can attempt to hack it.