Submission #384400

#	Time	Username	Problem	Language	Result	Execution time	Memory
384400		SansPapyrus683	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	682 ms	44408 KiB

commuter_pass

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

using std::cout;
using std::endl;
using std::vector;
using std::pair;

pair<vector<vector<int>>, vector<long long>> orig_min_costs(
    int from, const vector<vector<pair<int, int>>>& neighbors
) {
    vector<long long> min_cost(neighbors.size(), LLONG_MAX);
    vector<vector<int>> origins(neighbors.size());
    min_cost[from] = 0;
    origins[from] = {};

    std::priority_queue<pair<long long, int>> frontier;
    frontier.push({0, from});
    while (!frontier.empty()) {
        auto [given_cost, curr] = frontier.top();
        if (-min_cost[curr] != given_cost) {
            frontier.pop();
            continue;
        }
        frontier.pop();
        long long curr_cost = min_cost[curr];
        for (auto [n, nc] : neighbors[curr]) {
            if (curr_cost + nc < min_cost[n]) {
                origins[n] = {curr};
                min_cost[n] = curr_cost + nc;
                frontier.push({-(curr_cost + nc), n});
            } else if (curr_cost + nc == min_cost[n]) {
                origins[n].push_back(curr);
            }
        }
    }
    return {origins, min_cost};
}

class SubwaySys {
    private:
        typedef pair<long long, long long> MeetCost;
        const MeetCost INVALID{-1, -1};

        const vector<vector<pair<int, int>>> neighbors;
        const int pass_start;
        const int pass_end;
        vector<long long> start_min;
        vector<long long> end_min;
        vector<vector<int>> come_from;
        vector<MeetCost> prev_mins;
        
        void calc_mins(int at) {
            if (prev_mins[at] != INVALID) {
                return;
            }
            prev_mins[at] = {start_min[at], end_min[at]};
            for (int cf : come_from[at]) {
                calc_mins(cf);
                MeetCost path_best = {std::min(start_min[at], prev_mins[cf].first),
                                      std::min(end_min[at], prev_mins[cf].second)};
                if (path_best.first + path_best.second < prev_mins[at].first + prev_mins[at].second) {
                    prev_mins[at] = path_best;
                }
            }
        }
    public:
        SubwaySys(const vector<vector<pair<int, int>>>& neighbors, int pass_start, int pass_end)
                : neighbors(neighbors), pass_start(pass_start), pass_end(pass_end) {
            come_from = orig_min_costs(pass_start, neighbors).first;
        }

        long long min_cost(int start, int end) {
            prev_mins = vector<MeetCost>(neighbors.size(), INVALID);
            start_min = orig_min_costs(start, neighbors).second;
            end_min = orig_min_costs(end, neighbors).second;
            calc_mins(pass_end);
            return std::min(start_min[end], prev_mins[pass_end].first + prev_mins[pass_end].second);
        }
};

// 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<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});
    }
    cout << SubwaySys(neighbors, --pass_start, --pass_end).min_cost(--start, --end) << endl;
}

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