Submission #1247096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247096		imann	Robot (JOI21_ho_t4)	C++20	24 / 100	436 ms	14244 KiB

Main

#include <iostream>
#include <array>
#include <vector>
#include <map>
#include <queue>
#include <limits>

using ll = long long;

const int MAX_N = 100*1000 + 2;

struct AdjEdge {
    int toNode;
    int color;
    int price;
};

std::array<std::vector<AdjEdge>, MAX_N> graph;

int solve(int n, int m) {
    std::array<int, MAX_N> dists;
    dists.fill(std::numeric_limits<int>::max());
    using T = std::pair<int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
    pq.push({0, 0});
    dists[0] = 0;
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();
        if (dists[node] != dist)
            continue;
        std::map<int, int> colorPrice, minColorDist;
        for (auto adj : graph[node]) {
            colorPrice[adj.color] += adj.price;
            if (minColorDist.find(adj.color) != minColorDist.end())
                minColorDist[adj.color] = std::min(minColorDist[adj.color], dists[adj.toNode]);
            else
                minColorDist[adj.color] = dists[adj.toNode];
        }
        for (auto adj : graph[node]) {
            int newDist = dist + adj.price;
            newDist = std::min(newDist, dist + colorPrice[adj.color] - adj.price);
            if (minColorDist.find(adj.color) != minColorDist.end() && minColorDist[adj.color] != std::numeric_limits<int>::max()) {
                newDist = std::min(newDist, minColorDist[adj.color] + colorPrice[adj.color] - adj.price);
            }
            if (newDist < dists[adj.toNode]) {
                dists[adj.toNode] = newDist;
                pq.push({newDist, adj.toNode});
            }
        }
    }
    return dists[n - 1];
}

int main() {
    int n, m; std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c, p; std::cin >> a >> b >> c >> p; a--; b--; c--;
        graph[a].push_back({b, c, p});
        graph[b].push_back({a, c, p});
    }
    int res = solve(n, m);
    if (res == std::numeric_limits<int>::max()) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << res << std::endl;
    }
}

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