제출 #381316

#제출 시각아이디문제언어결과실행 시간메모리
381316SansPapyrus683Robot (JOI21_ho_t4)C++17
0 / 100
3074 ms54268 KiB
#include <iostream> #include <vector> #include <tuple> #include <queue> #include <unordered_map> #include <climits> using std::cout; using std::get; 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; color_neighbors[--from][color].push_back({--to, change_cost}); color_neighbors[to][color].push_back({from, change_cost}); } vector<std::unordered_map<int, long long>> min_cost(crossing_num); min_cost[0][-1] = 0; std::priority_queue<pair<long long, pair<int, int>>> frontier; frontier.push({0, {0, -1}}); while (!frontier.empty()) { pair<int, int> curr = frontier.top().second; long long curr_cost = min_cost[curr.first][curr.second]; if (-frontier.top().first != curr_cost) { continue; } 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)); for (auto const& [n, nc] : n_list) { long long new_cost = curr_cost + nc; if (min_cost[n].find(c) == min_cost[n].end() || new_cost < min_cost[n][c]) { min_cost[n][c] = new_cost; frontier.push({-new_cost, {n, c}}); } if (need_change) { continue; } if (min_cost[n].find(-1) == min_cost[n].end() || curr_cost < min_cost[n][-1]) { min_cost[n][-1] = curr_cost; frontier.push({-curr_cost, {n, -1}}); } } } } cout << -1 << endl; end:; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...