Submission #380671

#	Time	Username	Problem	Language	Result	Execution time	Memory
380671		SansPapyrus683	Robot (JOI21_ho_t4)	C++17	0 / 100	513 ms	43516 KiB

Main

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

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;
        color_neighbors[--from][color].push_back({--to, change_cost});
        color_neighbors[to][color].push_back({from, change_cost});
    }
    
    vector<vector<pair<int, int>>> neighbors;
    for (const std::unordered_map<int, vector<pair<int, int>>>& r_list : color_neighbors) {
        vector<pair<int, int>> rn_adj;
        for (auto const& [c, n] : r_list) {
            if (n.size() == 1) {
                rn_adj.push_back({n[0].first, 0});
            } else {
                rn_adj.insert(rn_adj.end(), n.begin(), n.end());
            }
        }
        neighbors.push_back(rn_adj);
    }

    vector<long long> min_cost(crossing_num, LLONG_MAX);
    min_cost[0] = 0;
    std::priority_queue<pair<long long, int>> frontier;
    frontier.push({0, 0});
    while (!frontier.empty()) {
        int curr = frontier.top().second;
        frontier.pop();
        for (auto const& [n, nc] : neighbors[curr]) {
            int new_cost = min_cost[curr] + nc;
            if (new_cost < min_cost[n]) {
                min_cost[n] = new_cost;
                frontier.push({-new_cost, n});
            }
        }
    }
    cout << (min_cost[crossing_num - 1] == LLONG_MAX ? -1 : min_cost[crossing_num - 1]) << endl;
}

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