제출 #380308

#제출 시각아이디문제언어결과실행 시간메모리
380308SansPapyrus683Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
782 ms13688 KiB
#include <iostream> #include <vector> #include <queue> #include <climits> #include <algorithm> using std::cout; using std::endl; using std::vector; vector<long long> raw_min_costs(int from, const vector<vector<std::pair<int, int>>>& neighbors) { vector<long long> min_cost(neighbors.size(), LLONG_MAX); min_cost[from] = 0; auto cmp = [&] (const int& a, const int& b) { return min_cost[a] > min_cost[b]; }; std::priority_queue<int, vector<int>, decltype(cmp)> frontier(cmp); frontier.push(from); while (!frontier.empty()) { int curr = frontier.top(); frontier.pop(); long long curr_cost = min_cost[curr]; for (auto [n, nc] : neighbors[curr]) { if (curr_cost + nc < min_cost[n]) { min_cost[n] = curr_cost + nc; frontier.push(n); } } } return min_cost; } long long min_cost(const vector<vector<std::pair<int, int>>>& neighbors, int from, int to, const vector<long long>& start_min, const vector<long long>& end_min, long long total_min) { vector<long long> min_cost(neighbors.size(), LLONG_MAX); min_cost[from] = 0; auto cmp = [&] (const int& a, const int& b) { return min_cost[a] > min_cost[b]; }; std::priority_queue<int, vector<int>, decltype(cmp)> frontier(cmp); frontier.push(from); while (!frontier.empty()) { int curr = frontier.top(); frontier.pop(); long long curr_cost = min_cost[curr]; if (curr == to) { return curr_cost; } for (auto [n, nc] : neighbors[curr]) { long long new_cost = curr_cost; if (start_min[curr] + nc + end_min[n] > total_min) { new_cost += nc; } if (new_cost < min_cost[n]) { min_cost[n] = new_cost; frontier.push(n); } } } return LLONG_MAX; } // https://oj.uz/problem/view/JOI18_commuter_pass (input ommitted due to length) int main() { int station_num; int railway_num; std::cin >> station_num >> railway_num; // i'll make all of these 0-indexed later in the code int pass_start; int pass_end; std::cin >> pass_start >> pass_end; int start; int end; std::cin >> start >> end; vector<vector<std::pair<int, int>>> neighbors(station_num); for (int r = 0; r < railway_num; r++) { int from; int to; int cost; std::cin >> from >> to >> cost; neighbors[--from].push_back({--to, cost}); neighbors[to].push_back({from, cost}); } vector<long long> start_min = raw_min_costs(--pass_start, neighbors); vector<long long> end_min = raw_min_costs(--pass_end, neighbors); long long total_min = start_min[pass_end]; // or end_min[pass_start], doesn't matter start--; end--; cout << std::min( min_cost(neighbors, start, end, start_min, end_min, total_min), min_cost(neighbors, start, end, end_min, start_min, total_min) ) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...