I am having problem writing a custom comparator for priority queue in C++. The elements' type in the queue is pair<long long,pair<long long, long long>> I want the queue to rank the elements with the smallestfirst element first, and if there is a tie, rank the elements with the smallest second.first element first. If there's a tie again, rank the element with the smallest second.second element first. So I have the following comparator and declaration:

class cmp {
public:
	bool operator()(pair<long long, pair<long long, long long>> A, pair<long long, pair<long long, long long>> B) {
		if (A.first > B.first) {
			return true;
		}
		if (A.first < B.first) {
			return false;
		}
		if (A.first == B.first) {
			if (A.second.first > B.second.first) {
				return true;
			}
			if (A.second.first < B.second.first) {
				return false;
			}
			if (A.second.second > B.second.second) {
				return false;
			}
			return true;
		}
	}
};

int main()
{
	priority_queue<pair<long long, pair<long long, long long>>,vector<pair<long long,pair<long long,long long>>>,cmp> q;
	q.push(make_pair(0, make_pair(1, 1)));//first element
	q.push(make_pair(9, make_pair(1, 1)));//second element
	q.push(make_pair(0, make_pair(1, 2)));//third element
}

However, when I push the three elements shown in the code, the queue does not give me the correct ranking of first, third, and second. I am sure I made some mistake but I couldn't find it. Please help me. Thank you!

Hi all, I am trying to code up a solution to the "Seating" problem in USACO January 2013 Gold, which uses a segment tree with lazy propagation. My code passes the first 2 test cases, but fails the rest. I have checked multiple times about my code but I don't see the problem.

#include<iostream>
#include<fstream>
#include<algorithm>
#include<assert.h>
#include<string>
#include<vector>
using namespace std;
int n, m;
int t;
vector<int> A;
vector<int> l0, r0, lazy0, lazy1,ans;

void build(int a,int l,int r) {
	if (r - l < 1) {
		l0[a] = 1;
		r0[a] = 1;
		ans[a] = 1;
		return;
	}
	l0[a] = r - l + 1;
	r0[a] = r - l + 1;
	ans[a] = r - l + 1;
	build(a * 2, l, (r + l) / 2);
	build(a * 2 + 1, (r + l) / 2 + 1, r);
}
void lazyupdate(int a,int l,int r) {
	assert(!(lazy0[a]==1&& lazy1[a]));
	if (lazy0[a]) {
		lazy0[a] = 0;
		l0[a] =ans[a]= r - l + 1;
		r0[a] = r - l + 1;
		if (l != r) { lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1; lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0; }
	}
	else if (lazy1[a]) {
		l0[a] = ans[a]=r0[a] = 0;
		if (l != r) { lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0; }
		lazy1[a] = 0;
	}
}
void updateint(int a, int l, int r) {
	int left = 2 * a, right = 2 * a + 1;
	l0[a] = ans[a] = r0[a] = 0;
	if (l0[left] == ((l + r) / 2 - l + 1)) {
		l0[a] = max(l0[a], max(l0[left], l0[left] + l0[right]));
	}
	else l0[a] = max(l0[a], l0[left]);
	if (r0[right] == (r - (l + r) / 2)) {
		r0[a] = max(r0[a], r0[right] + r0[left]);
	}
	else r0[a] = max(l0[a], r0[right]);
	ans[a] = max(r0[a], max(l0[a], r0[left] + l0[right]));
}
void update0(int i, int j,int a=1, int l=0, int r=n-1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;
	
	if (l >= i&&r <= j) {
		l0[a] = r - l + 1;
		r0[a] =ans[a]= r - l + 1;
		if (l == r)return;
		lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1;
		lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update0(i, j, left, l, (l + r) / 2);
	update0(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);

}
void update1(int i, int j, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;

	if (l >= i&&r <= j) {
		l0[a] = 0;
		r0[a] = 0;
		ans[a] = 0;
		if (l == r)return;
		lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; 
		lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update1(i, j, left, l, (l + r) / 2);
	update1(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);
}
pair<int,int> getint(int num, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if(l!=r)lazyupdate(2 * a, l, (l + r) / 2);
	if(l!=r)lazyupdate(2 * a + 1, (l + r) / 2 + 1, r);
	if (ans[a] == num&&r-l+1==num) {
		return pair<int, int>(l, r);
	}
	int left = 2 * a, right = 2 * a + 1;
	if (ans[left] >= num) {
		return getint(num, a * 2, l, (l + r) / 2);
	}

	if (r0[left] + l0[right] >= num&&r0[left]!=0) {
			int need = num - r0[left];
			pair<int, int> p1;
			p1.first = (l + r) / 2 - r0[left] + 1;
			p1.second = (l + r) / 2 + need;
			
			return p1;
	}
	if (ans[right]>=num) {
		return getint(num, a * 2 + 1, (l + r) / 2 + 1, r);
	}
	assert(0);
}
int main() {
	ifstream fin("seating.in");
	ofstream fout("seating.out");
	fin >> n >> m;
	l0, r0, lazy0, lazy1, ans;
	A.resize(n);
	l0.resize(4 * n); r0.resize(4 * n); lazy0.resize(4 * n); lazy1.resize(4 * n); ans.resize(4 * n);
	build(1, 0, n - 1);
	int res = 0;
	for (int i = 0; i < m; i++) {

		string stat;
		fin >> stat;
		if (stat[0] == 'A') {
			int add; fin >> add;
			if (ans[1] < add) {
				res++;
				continue;
			}
			pair<int, int> p = getint(add);
			update1(p.first, p.second);
		}
		else {
			int from, to; fin >> from >> to;
			from--; to--;
			update0(from, to);
		}
	}
	fout << res << endl;
	return 0;
}

In my segment tree, update0 updates a given range of values to 0,update1 updates a given range of values to 1, updateint updates the interval whenever some of its values have changed.getInt(add) gets the lowest position to insert the group of people. lazy0 andlazy1 stores respectively the lazy propagation for setting to 0 and setting to 1. Thank you so much for your help.

(First time writing a blog, sorry for any confusions)

Normally, in a shortest-path problem, the distance from one node to another node usually is determined by only one variable (usually the "cost" of that edge), which can be implemented by maintaining a priority queue of nodes based on the values of the edges.

Recently I encountered a USACO Problem (link here: where the cost between an edge depend on two variables: the latency of the pipes, and the minimum capacity of the pipes. While the problem solution provided by USACO tells us to consider latency and capacity separately (by iterating over all possible capacities and run Dijkstra on edges that have at least that capacity), I wonder if it is possible to use just one Dijkstra search, while considering both variables at the same time. Here is my code:

#include<iostream>
#include<fstream>
#include<queue>
#include<math.h>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;
#define mp make_pair
#define MAX 1e9
int n, m, x;
class sss {
public:
	double lat, cap;
	sss(double n1, double n2) {
		lat = n1, cap = n2;
	}
	double calct() {
		return lat + x / cap;
	}
};
class cmpsss {
public:
	bool operator()(pair<sss,int>c1, pair<sss,int>c2) {
		return c1.first.calct() > c2.first.calct();
	}
};
vector<pair<int,pair<int, int>>>neibs[501];

double dist[501];
void dijk() {
	for (int i = 0; i <= n; i++) {
		dist[i] = MAX;
	}
	dist[1] = 0;
	priority_queue<pair<sss, int>, vector<pair<sss, int>>, cmpsss> q;
	q.push(mp(sss(0, MAX), 1));
	while (!q.empty()) {
		pair<sss, int> nownode = q.top(); q.pop();
		int cur = nownode.second;
		double curlat = nownode.first.lat;
		double curcap = nownode.first.cap;
		if (dist[cur] < nownode.first.calct()&&cur!=1)continue;
		for (int i = 0; i < neibs[cur].size(); i++) {
			int next = neibs[cur][i].first;
			double nextlat = neibs[cur][i].second.first;
			double nextcap = min(int(curcap), neibs[cur][i].second.second);
			if (dist[next] > curlat + nextlat + x / nextcap) {
				dist[next] = curlat + nextlat + x / nextcap;
				q.push(mp(sss(nextlat, nextcap), next));
			}
		}
	}
}
int main() {
	ifstream fin("mroute.in");
	ofstream fout("mroute.out");
	fin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		int node1, node2, cost, cap;
		fin >> node1 >> node2 >> cost >> cap;
		neibs[node1].push_back(mp(node2, mp(cost,cap)));
		neibs[node2].push_back(mp(node1, mp(cost,cap)));
	
	}
	dijk();
	fout << floor(dist[n]) << endl;
	return 0;

}

In my code, I wrote a class called sss to store both the latency and the capacity. The member function calct() calculates the combined cost of both variables, given the edge. The priority queue compares two nodes using the same function calct(). However, this did not work when I submitted it online. Is my solution wrong, or Dijkstra just does not work when the cost is determined by two variables? Thanks.