Submission #379932

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

commuter_pass

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

// #include "debugging.h"

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;
}

// 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);
    int total_min = start_min[pass_end];  // or end_min[pass_start], doesn't matter

    vector<long long> min_cost(station_num, LLONG_MAX);
    min_cost[--start] = 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(start);
    end--;
    while (!frontier.empty()) {
        int curr = frontier.top();
        frontier.pop();
        if (curr == end) {
            break;
        }
        long long curr_cost = min_cost[curr];
        for (auto [n, nc] : neighbors[curr]) {
            long long new_cost = curr_cost;
            if (start_min[curr] + nc + end_min[n] > total_min && end_min[curr] + nc + start_min[n] > total_min) {
                new_cost += nc;
            }
            // cout << vector<int>{curr, n, (int) curr_cost, (int) new_cost} << endl;
            if (new_cost < min_cost[n]) {
                min_cost[n] = new_cost;
                frontier.push(n);
            }
        }
    }
    // cout << start_min << endl;
    // cout << end_min << endl << endl;
    // cout << min_cost << endl;
    cout << min_cost[end] << endl;
}

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