#include <iostream>
#include <stdexcept>
#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>>>> color_neighbors(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;
if (color == 0) {
throw std::invalid_argument("sorry but i can't take colors with a value of 0");
}
color_neighbors[--from][color].push_back({--to, change_cost});
color_neighbors[to][color].push_back({from, change_cost});
}
vector<vector<long long>> min_cost(crossing_num, vector<long long>(2, LLONG_MAX));
min_cost[0][false] = 0;
std::priority_queue<pair<long long, pair<int, int>>> frontier;
frontier.push({0, {0, false}});
while (!frontier.empty()) {
pair<int, int> curr = frontier.top().second;
long long curr_cost = min_cost[curr.first][(bool) curr.second];
if (-frontier.top().first != curr_cost) {
continue;
}
// cout << curr << ' ' << curr_cost << " ###################" << endl;
if (curr.first == crossing_num - 1) {
cout << curr_cost << endl;
goto end;
}
frontier.pop();
for (auto const& [c, n_list] : color_neighbors[curr.first]) {
bool need_change = n_list.size() > (1 + (c == curr.second));
// cout << n_list << ' ' << need_change << endl;
for (auto const& [n, nc] : n_list) {
long long new_cost = curr_cost + nc;
if (new_cost < min_cost[n][true]) {
min_cost[n][true] = new_cost;
// cout << std::make_pair(n, c) << ' ' << new_cost << endl;
frontier.push({-new_cost, {n, c}});
}
if (need_change) {
continue;
}
if (curr_cost < min_cost[n][false]) {
min_cost[n][false] = curr_cost;
// cout << std::make_pair(n, c) << ' ' << new_cost << endl;
frontier.push({-curr_cost, {n, 0}});
}
}
}
}
cout << -1 << endl;
end:;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Execution timed out |
3064 ms |
384 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
177 ms |
10604 KB |
Output is correct |
2 |
Correct |
69 ms |
6020 KB |
Output is correct |
3 |
Correct |
215 ms |
8300 KB |
Output is correct |
4 |
Correct |
101 ms |
8044 KB |
Output is correct |
5 |
Incorrect |
594 ms |
37768 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Execution timed out |
3064 ms |
384 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |