제출 #381317

#제출 시각아이디문제언어결과실행 시간메모리
381317SansPapyrus683Robot (JOI21_ho_t4)C++17
0 / 100
3064 ms37768 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...