Submission #1152852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152852		batpurev	Robot (JOI21_ho_t4)	C++20	0 / 100	171 ms	21448 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;

struct edge {
    ll to, color, cost;
};

int n, m;
vector<vector<edge>> adj;
vector<ll> dist, sum, best;

const ll inf = 1e18;

int dijkstra() {
    priority_queue<pair<ll, ll>> pq;
    dist[1] = 0;
    pq.push({0LL, 1LL});
    while (!pq.empty()) {
        ll u = pq.top().second;
        ll curr = -pq.top().first;
        pq.pop();
        if (curr != dist[u]) continue;
        for (edge &e: adj[u]) {
            sum[e.color] += e.cost;
            best[e.color] = min(best[e.color], dist[e.to]);
        }
        for (edge &e: adj[u]) {
            ll color = e.color;
            ll v = e.to;
            ll cost = e.cost;
            ll w = min(cost, sum[color] - cost);
            if (dist[v] > curr + w) {
                dist[v] = curr + w;
                pq.push({-dist[v], v});
            }
            if (dist[v] > best[color] + sum[color] - w) {
                dist[v] = best[color] + sum[color] - w;
                pq.push({-dist[v], v});
            }
        }
        for (edge &e: adj[u]) {
            sum[e.color] = 0;
            best[e.color] = inf;
        }
    }
    return dist[n];
}

int main() {
    cin >> n >> m;
    adj.resize(n + 1);
    best.resize(m + 1, inf);
    dist.resize(n + 1, inf);
    sum.resize(m + 1, 0);
    for (int i = 0; i<m; ++i) {
        ll u, v, color, cost;
        cin >> u >> v >> color >> cost;
        edge a = {v, color, cost};
        edge b = {u, color, cost};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }
    cout << dijkstra() << '\n';
}

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