This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |