CSES Investigation

Debugging Help
#1

Problem Info

Here

My Work

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <climits>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

constexpr int MOD = 1e9 + 7;

vector<long long> shortest_num;  // god forgive me
vector<int> least_flights;
vector<int> most_flights;

void calc_path_info(int at, const vector<std::set<int>>& prev) {
    if (shortest_num[at] != -1) {
        // if this one was calculated, same for the other 2 as well
        return;
    }
    least_flights[at] = INT_MAX;
    most_flights[at] = INT_MIN;
    shortest_num[at] = 0;
    for (int p : prev[at]) {
        calc_path_info(p, prev);
        shortest_num[at] = (shortest_num[at] + shortest_num[p]) % MOD;
        least_flights[at] = std::min(least_flights[at], least_flights[p] + 1);
        most_flights[at] = std::max(most_flights[at], most_flights[p] + 1);
    }
}

// https://cses.fi/problemset/task/1202 (input ommitted due to length)
int main() {
    int city_num;
    int flight_num;
    std::cin >> city_num >> flight_num;
    vector<vector<std::pair<int, int>>> neighbors(city_num);
    for (int f = 0; f < flight_num; f++) {
        int from;
        int to;
        int cost;
        std::cin >> from >> to >> cost;
        neighbors[--from].push_back({--to, cost});
    }

    vector<long long> min_cost(neighbors.size(), LLONG_MAX);
    vector<std::set<int>> origins(neighbors.size());
    min_cost[0] = 0;
    origins[0] = {};

    auto cmp = [&] (const int& a, const int& b) { return min_cost[a] > min_cost[b]; }; 
    std::priority_queue<int, vector<int>, decltype(cmp)> frontier(cmp);
    frontier.push(0);
    while (!frontier.empty()) {
        int curr = frontier.top();
        frontier.pop();
        long long curr_cost = min_cost[curr];
        for (auto [n, nc] : neighbors[curr]) {
            if (curr_cost + nc < min_cost[n]) {
                origins[n] = {curr};
                min_cost[n] = curr_cost + nc;
                frontier.push(n);
            } else if (curr_cost + nc == min_cost[n]) {
                origins[n].insert(curr);
            }
        }
    }

    shortest_num = vector<long long>(city_num, -1);
    least_flights = vector<int>(city_num, -1);
    most_flights = vector<int>(city_num, -1);
    shortest_num[0] = 1;
    least_flights[0] = most_flights[0] = 0;
    calc_path_info(city_num - 1, origins);

    cout << min_cost[city_num - 1] << ' ' << shortest_num[city_num - 1] << ' ' << least_flights[city_num - 1] << ' ' << most_flights[city_num - 1] << endl;
}

I’ve looked at the solution, and it’s essentially the same thing.

What I’ve Tried

This only WAs on 2 (very large) test cases, making it nearly impossible to debug, and I’ve done some small checks for overflow. The Dijkstra’s also worked for another problem, so it can’t be the origin variable that’s wrong.

Question

Why does this WA for the number of shortest paths?

#2

I ended up peeking at the solution, and changed some details in the implementation. The thing is, for some reason this code gets two test cases wrong, while this code gets AC’d.

I see virtually no difference (other than one using a lambda and the other using pairs), so why do they output different results?

#3

Two elements of a priority queue should always have the same ordering relative to each other while they are both present in the queue. Your first solution violates this precondition … (changing min_cost changes the relative ordering).

#4

Yeah, but from my experience 80% of the time Dijkstra’s works with that min_cost array as well. Is this just the result of dumb luck?

#5

To understand priority_queue more deeply you should read about its underlying data structure, the heap. It is possible to implement Dijkstra’s with a heap that supports modifying elements, but it would require writing your own heap functions.

Modifying min_cost can not only give WA in some cases, but also will make your code slower as you pop nodes off the in wrong order. Also you don’t need a visited array to implement Dijkstra’s, just compare the distance from the heap with the distance in the array.

#6

Ok, but again,

from my experience 80% of the time Dijkstra’s works with that min_cost array as well. Is this just the result of dumb luck?

Also, when I removed the visited array, it gets WA on 3 test cases.

#7

Yes.

Here’s an implementation of Dijkstra’s (taken from commuter pass):

auto dijkstra = [&](vector<vector<pii> >& g, int a) {
	typedef pair<ll,int> point;
	vector<ll> dist(n, inf);
	priority_queue<point, vector<point>, greater<point> > pq;
	dist[a] = 0;
	pq.push({0ll, a});
	while (not pq.empty()) {
		auto [d, cur] = pq.top(); pq.pop();
		if (d != dist[cur]) continue;
		for (auto [nxt, w] : g[cur]) {
			if (setmin(dist[nxt], d + w)) {
				pq.push({dist[nxt], nxt});
			}
		}
	}
	return dist;
};
#8

So that “yes” was for all my ACs being dumb luck, right?

Also, when I removed the visited array, it gets WA on 3 test cases.