#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
#include "debugging.h"
using std::cout;
using std::endl;
using std::vector;
using std::pair;
// https://oj.uz/problem/view/JOI21_ho_t4 (input ommitted due to length)
int main() {
int crossing_num;
int road_num;
std::cin >> crossing_num >> road_num;
vector<std::unordered_map<int, vector<pair<int, int>>>> neighbors(crossing_num);
vector<std::unordered_map<int, long long>> color_sums(crossing_num);
for (int r = 0; r < road_num; r++) {
int from;
int to;
int color;
int change_cost;
std::cin >> from >> to >> color >> change_cost;
neighbors[--from][color].push_back({--to, change_cost});
neighbors[to][color].push_back({from, change_cost});
color_sums[from][color] += change_cost;
color_sums[to][color] += change_cost;
}
vector<std::unordered_map<int, long long>> min_cost(crossing_num);
min_cost[0][-1] = 0;
// a "node" will be represented as a position and the last color change (-1 if no change) along with its cost
std::priority_queue<pair<long long, pair<int, int>>> frontier;
frontier.push({0, {0, -1}});
while (!frontier.empty()) {
auto [at, prev_c] = frontier.top().second;
long long curr_cost = min_cost[at][prev_c];
if (-frontier.top().first != curr_cost) {
frontier.pop();
continue;
}
frontier.pop();
if (prev_c == -1) {
for (auto const& [c, n_list] : neighbors[at]) {
for (auto [n, n_cost] : n_list) {
long long flip_others = curr_cost + color_sums[at][c] - n_cost;
if (!min_cost[n].count(-1) || flip_others < min_cost[n][-1]) {
min_cost[n][-1] = flip_others;
frontier.push({-flip_others, {n, -1}});
}
long long flip_this = curr_cost + n_cost;
if (flip_this < min_cost[n][-1]) { // no membership check needed
min_cost[n][-1] = flip_this;
frontier.push({-flip_this, {n, -1}});
}
long long no_change = curr_cost;
if (!min_cost[n].count(c) || no_change < min_cost[n][c]) {
min_cost[n][c] = no_change;
frontier.push({-no_change, {n, c}});
}
}
}
} else {
for (auto [n, n_cost] : neighbors[at][prev_c]) {
long long flip_others = curr_cost + color_sums[at][prev_c] - n_cost;
if (!min_cost[n].count(prev_c) || flip_others < min_cost[n][prev_c]) {
min_cost[n][prev_c] = flip_others;
frontier.push({-flip_others, {n, -1}});
}
}
}
}
cout << (!min_cost[crossing_num - 1].count(-1) ? -1 : min_cost[crossing_num - 1][-1]) << endl;
}
Compilation message
Main.cpp:7:10: fatal error: debugging.h: No such file or directory
7 | #include "debugging.h"
| ^~~~~~~~~~~~~
compilation terminated.
