Submission #1247098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247098		imann	Robot (JOI21_ho_t4)	C++20	100 / 100	453 ms	24600 KiB

Main

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

using ll = long long;

const ll MAX_N = 100*1000 + 2;

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

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

ll solve(ll n, ll m) {
    std::array<ll, MAX_N> dists;
    dists.fill(std::numeric_limits<ll>::max());
    using T = std::pair<ll, ll>;
    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<ll, ll> 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]) {
            ll 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<ll>::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() {
    ll n, m; std::cin >> n >> m;
    for (ll i = 0; i < m; ++i) {
        ll 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});
    }
    ll res = solve(n, m);
    if (res == std::numeric_limits<ll>::max()) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << res << std::endl;
    }
}

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