oj.uz

답안 #380438

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380438 2021-03-21T19:16:19 Z SansPapyrus683 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 1953 ms 44864 KB 
#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] = {};

    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]) {
                origins[n] = {curr};
                min_cost[n] = curr_cost + nc;
                frontier.push(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{LLONG_MAX, LLONG_MAX};

        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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 39948 KB Output is correct
2 Correct 717 ms 39796 KB Output is correct
3 Correct 1090 ms 44096 KB Output is correct
4 Correct 595 ms 39856 KB Output is correct
5 Correct 678 ms 39900 KB Output is correct
6 Correct 602 ms 39660 KB Output is correct
7 Correct 753 ms 39672 KB Output is correct
8 Correct 727 ms 39576 KB Output is correct
9 Correct 607 ms 40172 KB Output is correct
10 Correct 489 ms 40312 KB Output is correct
11 Correct 290 ms 36288 KB Output is correct
12 Correct 623 ms 39916 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1374 ms 42180 KB Output is correct
2 Correct 1926 ms 42564 KB Output is correct
3 Correct 1875 ms 42504 KB Output is correct
4 Correct 1869 ms 42692 KB Output is correct
5 Correct 1953 ms 43176 KB Output is correct
6 Correct 1158 ms 43768 KB Output is correct
7 Correct 1925 ms 44864 KB Output is correct
8 Correct 1947 ms 42776 KB Output is correct
9 Correct 1849 ms 42924 KB Output is correct
10 Correct 1943 ms 42668 KB Output is correct
11 Correct 315 ms 37664 KB Output is correct
12 Correct 1115 ms 43948 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2028 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 46 ms 3436 KB Output is correct
5 Correct 24 ms 1772 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 23 ms 1828 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 39948 KB Output is correct
2 Correct 717 ms 39796 KB Output is correct
3 Correct 1090 ms 44096 KB Output is correct
4 Correct 595 ms 39856 KB Output is correct
5 Correct 678 ms 39900 KB Output is correct
6 Correct 602 ms 39660 KB Output is correct
7 Correct 753 ms 39672 KB Output is correct
8 Correct 727 ms 39576 KB Output is correct
9 Correct 607 ms 40172 KB Output is correct
10 Correct 489 ms 40312 KB Output is correct
11 Correct 290 ms 36288 KB Output is correct
12 Correct 623 ms 39916 KB Output is correct
13 Correct 1374 ms 42180 KB Output is correct
14 Correct 1926 ms 42564 KB Output is correct
15 Correct 1875 ms 42504 KB Output is correct
16 Correct 1869 ms 42692 KB Output is correct
17 Correct 1953 ms 43176 KB Output is correct
18 Correct 1158 ms 43768 KB Output is correct
19 Correct 1925 ms 44864 KB Output is correct
20 Correct 1947 ms 42776 KB Output is correct
21 Correct 1849 ms 42924 KB Output is correct
22 Correct 1943 ms 42668 KB Output is correct
23 Correct 315 ms 37664 KB Output is correct
24 Correct 1115 ms 43948 KB Output is correct
25 Correct 23 ms 2028 KB Output is correct
26 Correct 2 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 46 ms 3436 KB Output is correct
29 Correct 24 ms 1772 KB Output is correct
30 Correct 2 ms 492 KB Output is correct
31 Correct 3 ms 492 KB Output is correct
32 Correct 5 ms 620 KB Output is correct
33 Correct 2 ms 492 KB Output is correct
34 Correct 23 ms 1828 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 2 ms 492 KB Output is correct
39 Correct 2 ms 492 KB Output is correct
40 Correct 611 ms 40028 KB Output is correct
41 Correct 606 ms 40144 KB Output is correct
42 Correct 635 ms 40020 KB Output is correct
43 Correct 333 ms 36896 KB Output is correct
44 Correct 317 ms 36816 KB Output is correct
45 Correct 681 ms 39388 KB Output is correct
46 Correct 658 ms 39320 KB Output is correct
47 Correct 629 ms 39888 KB Output is correct
48 Correct 324 ms 34080 KB Output is correct
49 Correct 576 ms 39572 KB Output is correct
50 Correct 702 ms 39560 KB Output is correct
51 Correct 623 ms 39316 KB Output is correct