## Problem Info

## 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?