oj.uz

답안 #384400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384400 2021-04-01T15:03:55 Z SansPapyrus683 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 682 ms 44408 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] = {};

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

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 40496 KB Output is correct
2 Correct 579 ms 40020 KB Output is correct
3 Correct 637 ms 44408 KB Output is correct
4 Correct 580 ms 41584 KB Output is correct
5 Correct 614 ms 39732 KB Output is correct
6 Correct 647 ms 40804 KB Output is correct
7 Correct 589 ms 40036 KB Output is correct
8 Correct 559 ms 40124 KB Output is correct
9 Correct 568 ms 40852 KB Output is correct
10 Correct 545 ms 40716 KB Output is correct
11 Correct 313 ms 36256 KB Output is correct
12 Correct 592 ms 40816 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 597 ms 42000 KB Output is correct
2 Correct 604 ms 41796 KB Output is correct
3 Correct 617 ms 41412 KB Output is correct
4 Correct 682 ms 41792 KB Output is correct
5 Correct 655 ms 42308 KB Output is correct
6 Correct 620 ms 43820 KB Output is correct
7 Correct 624 ms 43972 KB Output is correct
8 Correct 635 ms 41844 KB Output is correct
9 Correct 659 ms 42196 KB Output is correct
10 Correct 629 ms 41556 KB Output is correct
11 Correct 343 ms 37648 KB Output is correct
12 Correct 622 ms 43968 KB Output is correct

Subtask #3
24.0 / 24.0

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

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 40496 KB Output is correct
2 Correct 579 ms 40020 KB Output is correct
3 Correct 637 ms 44408 KB Output is correct
4 Correct 580 ms 41584 KB Output is correct
5 Correct 614 ms 39732 KB Output is correct
6 Correct 647 ms 40804 KB Output is correct
7 Correct 589 ms 40036 KB Output is correct
8 Correct 559 ms 40124 KB Output is correct
9 Correct 568 ms 40852 KB Output is correct
10 Correct 545 ms 40716 KB Output is correct
11 Correct 313 ms 36256 KB Output is correct
12 Correct 592 ms 40816 KB Output is correct
13 Correct 597 ms 42000 KB Output is correct
14 Correct 604 ms 41796 KB Output is correct
15 Correct 617 ms 41412 KB Output is correct
16 Correct 682 ms 41792 KB Output is correct
17 Correct 655 ms 42308 KB Output is correct
18 Correct 620 ms 43820 KB Output is correct
19 Correct 624 ms 43972 KB Output is correct
20 Correct 635 ms 41844 KB Output is correct
21 Correct 659 ms 42196 KB Output is correct
22 Correct 629 ms 41556 KB Output is correct
23 Correct 343 ms 37648 KB Output is correct
24 Correct 622 ms 43968 KB Output is correct
25 Correct 24 ms 1900 KB Output is correct
26 Correct 2 ms 364 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 56 ms 3436 KB Output is correct
29 Correct 23 ms 1772 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 4 ms 492 KB Output is correct
32 Correct 7 ms 620 KB Output is correct
33 Correct 3 ms 492 KB Output is correct
34 Correct 29 ms 1772 KB Output is correct
35 Correct 2 ms 364 KB Output is correct
36 Correct 2 ms 364 KB Output is correct
37 Correct 2 ms 364 KB Output is correct
38 Correct 3 ms 492 KB Output is correct
39 Correct 3 ms 492 KB Output is correct
40 Correct 598 ms 41328 KB Output is correct
41 Correct 644 ms 40804 KB Output is correct
42 Correct 586 ms 40736 KB Output is correct
43 Correct 362 ms 36840 KB Output is correct
44 Correct 363 ms 36920 KB Output is correct
45 Correct 613 ms 39932 KB Output is correct
46 Correct 627 ms 39432 KB Output is correct
47 Correct 587 ms 41420 KB Output is correct
48 Correct 351 ms 34032 KB Output is correct
49 Correct 661 ms 40852 KB Output is correct
50 Correct 630 ms 39584 KB Output is correct
51 Correct 618 ms 40020 KB Output is correct