Submission #380275

#	Time	Username	Problem	Language	Result	Execution time	Memory
380275		SansPapyrus683	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2084 ms	262148 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
 
vector<long long> origin_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 = origin_min_costs(--pass_start, neighbors);
    vector<long long> end_min = origin_min_costs(--pass_end, neighbors);
    long long total_min = start_min[pass_end];  // or end_min[pass_start], doesn't matter
    start--;
    end--;
    long long ans = std::min(
        min_cost(neighbors, start, end, start_min, end_min, total_min),
        min_cost(neighbors, start, end, end_min, start_min, total_min)
    );
    cout << ans << endl;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45