제출 #1152710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152710		batpurev	Robot (JOI21_ho_t4)	C++20	100 / 100	96 ms	22652 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;
struct edge {
	ll to, color, cost;
	edge(){}
	edge(ll a, ll b, ll c) {
		to = a;
		color = b;
		cost = c;
	}
};

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});
	while (pq.size()) {
		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 to = e.to;
			ll color = e.color;
			ll w = e.cost;
			ll tmp = min(0LL + w, sum[color] - w);
			if (dist[to] > curr + tmp) {
                dist[to] = curr + tmp;
                pq.push({-dist[to], to});
            }

			if (dist[to] > best[color] + sum[color] - w) {
                dist[to] = best[color] + sum[color] - w;
				pq.push({-dist[to], to});
            }
		}

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

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

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

    adj.resize(n + 1);
    dist.resize(2 * n + 1);
    sum.resize(m + 1);
    best.resize(m + 1);

	for (ll i = 1; i<=m; ++i) {
		ll u, v, color, cost;
		cin >> u >> v >> color >> cost;
		edge a = edge(v, color, cost);
		edge b = edge(u, color, cost);
		adj[u].push_back(a);
		adj[v].push_back(b);
	}
	for (ll i = 1; i<=n; ++i) dist[i] = INF;
	for (ll i = 1; i<=m; ++i) best[i] = INF;

    cout << dijkstra() << '\n';
	return 0;
}

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