Submission #384711

#	Time	Username	Problem	Language	Result	Execution time	Memory
384711		SansPapyrus683	Robot (JOI21_ho_t4)	C++17	0 / 100	492 ms	21368 KiB

Main

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

// #include "debugging.h"

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

// 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<std::unordered_map<int, vector<pair<int, int>>>> 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][color].push_back({--to, change_cost});
        neighbors[to][color].push_back({from, 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, int>>> frontier;
    frontier.push({0, {0, -1}});
    while (!frontier.empty()) {
        auto [at, prev_c] = frontier.top().second;
        long long curr_cost = min_cost[at][prev_c];
        if (-frontier.top().first != curr_cost) {
            frontier.pop();
            continue;
        }
        frontier.pop();
        if (prev_c == -1) {
            for (auto const& [c, n_list] : neighbors[at]) {
                for (auto [n, n_cost] : n_list) {
                    long long flip_others = curr_cost + color_sums[at][c] - n_cost;
                    if (!min_cost[n].count(-1) || flip_others < min_cost[n][-1]) {
                        min_cost[n][-1] = flip_others;
                        frontier.push({-flip_others, {n, -1}});
                    }
                    long long flip_this = curr_cost + n_cost;
                    if (flip_this < min_cost[n][-1]) {  // no membership check needed
                        min_cost[n][-1] = flip_this;
                        frontier.push({-flip_this, {n, -1}});
                    }
                    long long no_change = curr_cost;
                    if (!min_cost[n].count(c) || no_change < min_cost[n][c]) {
                        min_cost[n][c] = no_change;
                        frontier.push({-no_change, {n, c}});
                    }
                }
            }
        } else {
            for (auto [n, n_cost] : neighbors[at][prev_c]) {
                long long flip_others = curr_cost + color_sums[at][prev_c] - n_cost;
                if (!min_cost[n].count(prev_c) || flip_others < min_cost[n][prev_c]) {
                    min_cost[n][prev_c] = flip_others;
                    frontier.push({-flip_others, {n, -1}});
                }
            }
        }
    }
    cout << (!min_cost[crossing_num - 1].count(-1) ? -1 : min_cost[crossing_num - 1][-1]) << endl;
}

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