Submission #381317

#	Time	Username	Problem	Language	Result	Execution time	Memory
381317		SansPapyrus683	Robot (JOI21_ho_t4)	C++17	0 / 100	3064 ms	37768 KiB

Main

#include <iostream>
#include <stdexcept>
#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>>>> color_neighbors(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;
        if (color == 0) {
            throw std::invalid_argument("sorry but i can't take colors with a value of 0");
        }
        color_neighbors[--from][color].push_back({--to, change_cost});
        color_neighbors[to][color].push_back({from, change_cost});
    }

    vector<vector<long long>> min_cost(crossing_num, vector<long long>(2, LLONG_MAX));
    min_cost[0][false] = 0;
    std::priority_queue<pair<long long, pair<int, int>>> frontier;
    frontier.push({0, {0, false}});
    while (!frontier.empty()) {
        pair<int, int> curr = frontier.top().second;
        long long curr_cost = min_cost[curr.first][(bool) curr.second];
        if (-frontier.top().first != curr_cost) {
            continue;
        }
        // cout << curr << ' ' << curr_cost << " ###################" << endl;
        if (curr.first == crossing_num - 1) {
            cout << curr_cost << endl;
            goto end;
        }
        frontier.pop();
        for (auto const& [c, n_list] : color_neighbors[curr.first]) {
            bool need_change = n_list.size() > (1 + (c == curr.second));
            // cout << n_list << ' ' << need_change << endl;
            for (auto const& [n, nc] : n_list) {
                long long new_cost = curr_cost + nc;
                if (new_cost < min_cost[n][true]) {
                    min_cost[n][true] = new_cost;
                    // cout << std::make_pair(n, c) << ' ' << new_cost << endl;
                    frontier.push({-new_cost, {n, c}});
                }
                if (need_change) {
                    continue;
                }
                if (curr_cost < min_cost[n][false]) {
                    min_cost[n][false] = curr_cost;
                    // cout << std::make_pair(n, c) << ' ' << new_cost << endl;
                    frontier.push({-curr_cost, {n, 0}});
                }
            }
        }
    }
    cout << -1 << endl;
    end:;
}

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