Блог пользователя ayushkoul00

Автор ayushkoul00, история, 3 года назад, По-английски

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;
}
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
	auto cmp = [&dist](const int &a, const int &b)
	{
		return dist[a] > dist[b];
	};

	priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

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 inside pq prior to the update, will not automatically reorder themselves based on the new value of dist[v].

More detailed explanation here.

I added my code with assertions:

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You 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.