Submission #1152876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152876		batpurev	Robot (JOI21_ho_t4)	C++20	100 / 100	93 ms	21744 KiB

Main

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

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

const ll inf = 1e18;
vector<vector<edge>> adj;
vector<ll> dist, sum, best;
ll n, m;

ll dijkstra() {
    dist[1] = 0;
	priority_queue<pair<ll, ll>> pq;
	pq.push({0, 1});
    vector<bool> vis(n + 1, false);
	while (pq.size()) {
		ll u = pq.top().second;
		ll curr = -pq.top().first;
		pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

		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 v = e.to;
			ll color = e.color;
			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] - cost) {
                dist[v] = best[color] + sum[color] - cost;
				pq.push({-dist[v], v});
            }
		}

		for (edge e : adj[u]) {
			sum[e.color] = 0;
			best[e.color] = inf;
		}
	}

	if (dist[n] == inf) return -1;
	return dist[n];
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;

    adj.resize(n + 1);
    dist.resize(n + 1, inf);
    sum.resize(m + 1);
    best.resize(m + 1, inf);

	for (ll i = 1; 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';
	return 0;
}

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