CSES - Shared codeLink to this code: https://cses.fi/paste/bbf5f66cb13a4fc71c8ab4/
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <algorithm>
// #include "debugging.h"
using std::cout;
using std::endl;
using std::vector;
constexpr int MOD = 1e9 + 7;
// 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<long long> shortest_num(city_num);
vector<int> least_flights(city_num);
vector<int> most_flights(city_num);
min_cost[0] = 0;
shortest_num[0] = 1;
vector<bool> visited(city_num);
std::priority_queue<std::pair<long long, int>> frontier;
frontier.push({0, 0});
while (!frontier.empty()) {
int curr = frontier.top().second;
frontier.pop();
long long curr_cost = min_cost[curr];
if (visited[curr]) {
continue;
}
visited[curr] = true;
for (auto [n, nc] : neighbors[curr]) {
long long new_cost = curr_cost + nc;
if (new_cost < min_cost[n]) {
shortest_num[n] = shortest_num[curr];
least_flights[n] = least_flights[curr] + 1;
most_flights[n] = most_flights[curr] + 1;
min_cost[n] = new_cost;
frontier.push({-new_cost, n});
} else if (new_cost == min_cost[n]) {
shortest_num[n] = (shortest_num[n] + shortest_num[curr]) % MOD;
least_flights[n] = std::min(least_flights[n], least_flights[curr] + 1);
most_flights[n] = std::max(most_flights[n], most_flights[curr] + 1);
frontier.push({-new_cost, n});
}
}
}
cout << min_cost[city_num - 1] << ' '
<< shortest_num[city_num - 1] << ' '
<< least_flights[city_num - 1] << ' '
<< most_flights[city_num - 1] << endl;
}