Code 1:
sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
return ((val[a.first]+val[a.second]) <= (val[b.first]+val[b.second]));
});
Code 2:
sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
return ((val[a.first]+val[a.second]) < (val[b.first]+val[b.second]));
});
These were a part of my solution to 2176D - Fibonacci Paths. The first code gave me runtime error on test case 8 but the later one is AC.
std::sort requires strict weak ordering, which means when comparing two equal objects the custom comparison function must return false. The reason for this being, under the hood std::sort uses < operator by default to compare two objects when no custom comparison function is given, hence when we do provide a custom function std::sort expects it to behave similar to the < operator. Using <= violates this expectation.









Because when you use
std::sortyou need to ensure there's no pair of element satisfycmp(a, b) && cmp(b, a).Because according to
std::sortintrosort implementation the final conclusion about comparator function is that: Ifcmp(a, b)istruethencmp(b, a)must befalse. But reverse rule is not necessary, means ifcmp(a, b)isfalsethencmp(b, a)does not have to be alwaystrueit can befalsealso. In-shortcmp(a, b)andcmp(b, a)can't be bothtrue, at least one of them has to befalse.