Submission #381316

#	Time	Username	Problem	Language	Result	Execution time	Memory
381316		SansPapyrus683	Robot (JOI21_ho_t4)	C++17	0 / 100	3074 ms	54268 KiB

Main

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

using std::cout;
using std::get;
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;
        color_neighbors[--from][color].push_back({--to, change_cost});
        color_neighbors[to][color].push_back({from, change_cost});
    }

    vector<std::unordered_map<int, long long>> min_cost(crossing_num);
    min_cost[0][-1] = 0;
    std::priority_queue<pair<long long, pair<int, int>>> frontier;
    frontier.push({0, {0, -1}});
    while (!frontier.empty()) {
        pair<int, int> curr = frontier.top().second;
        long long curr_cost = min_cost[curr.first][curr.second];
        if (-frontier.top().first != curr_cost) {
            continue;
        }
        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));
            for (auto const& [n, nc] : n_list) {
                long long new_cost = curr_cost + nc;
                if (min_cost[n].find(c) == min_cost[n].end() || new_cost < min_cost[n][c]) {
                    min_cost[n][c] = new_cost;
                    frontier.push({-new_cost, {n, c}});
                }
                if (need_change) {
                    continue;
                }
                if (min_cost[n].find(-1) == min_cost[n].end() || curr_cost < min_cost[n][-1]) {
                    min_cost[n][-1] = curr_cost;
                    frontier.push({-curr_cost, {n, -1}});
                }
            }
        }
    }
    cout << -1 << endl;
    end:;
}

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