Submission #384259

#	Time	Username	Problem	Language	Result	Execution time	Memory
384259		SansPapyrus683	Robot (JOI21_ho_t4)	C++17	0 / 100	3085 ms	50960 KiB

Main

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

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

struct Road {
    int to;
    int color;
    int change_cost;
};

// https://oj.uz/problem/view/JOI21_ho_t4 (input ommitted due to length)
int main() {
    int crossing_num;
    int road_num;
    std::cin >> crossing_num >> road_num;
    vector<vector<Road>> neighbors(crossing_num);
    vector<std::unordered_map<int, long long>> color_sums(crossing_num);
    for (int r = 0; r < road_num; r++) {
        int from;
        int to;
        int color;
        int change_cost;
        std::cin >> from >> to >> color >> change_cost;
        neighbors[--from].push_back({--to, color, change_cost});
        neighbors[to].push_back({from, color, change_cost});
        color_sums[from][color] += change_cost;
        color_sums[to][color] += change_cost;
    }
 
    vector<std::unordered_map<int, long long>> min_cost(crossing_num);
    min_cost[0][-1] = 0;
    // a "node" will be represented as a position and the last color change (-1 if no change) along with its cost
    std::priority_queue<pair<long long, pair<int, pair<int, int>>>> frontier;
    frontier.push({0, {0, {-1, 0}}});
    while (!frontier.empty()) {
        auto [at, prev_c] = frontier.top().second;
        long long curr_cost = min_cost[at][prev_c.first];
        if (-frontier.top().first != curr_cost) {
            frontier.pop();
            continue;
        }
        if (at == crossing_num - 1) {
            cout << curr_cost << endl;
            goto end;
        }
        frontier.pop();
        for (const Road& r : neighbors[at]) {
            long long change_this = curr_cost + r.change_cost;
            if (min_cost[r.to].find(r.color) == min_cost[r.to].end() || change_this < min_cost[r.to][r.color]) {
                min_cost[r.to][r.color] = change_this;
                frontier.push({-change_this, {r.to, {r.color, r.change_cost}}});
            }
            long long change_others = curr_cost + color_sums[at][r.color] - r.change_cost;
            if (prev_c.first == r.color) {
                change_others -= prev_c.second;
            }
            if (min_cost[r.to].find(-1) == min_cost[r.to].end() || change_others < min_cost[r.to][-1]) {
                min_cost[r.to][-1] = change_others;
                frontier.push({-change_others, {r.to, {-1, 0}}});
            }
        }
    }
    cout << -1 << endl;
    end:;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42