Submission #1219540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219540		trimkus	Robot (JOI21_ho_t4)	C++20	100 / 100	671 ms	91020 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN = 2e5;

ll dp[MAXN + 1];
map<int, ll> ps[MAXN + 1], dp2[MAXN + 1]; 
map<int, vector<array<int, 3>>> adj[MAXN + 1];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c, w;
		cin >> a >> b >> c >> w;
		adj[a][c].push_back({b, c, w});
		adj[b][c].push_back({a, c, w});
		ps[a][c] += w;
		ps[b][c] += w;
	}
	for (int i = 1; i <= n; ++i) {
		dp[i] = (ll)1e18;
	}
	priority_queue<array<ll, 3>> pq;
	pq.push({0, 1, 0});
	dp[1] = 0;
	while (pq.size()) {
		ll cost = -pq.top()[0];
		int v = pq.top()[1];
		int col = pq.top()[2];
		pq.pop();
		//~ cerr << v << " " << col << " = " << cost << "\n";
		if (col) {
			if (dp2[v][col] != cost) continue;
			for (auto& [u, c, w] : adj[v][col]) {
				ll cost1 = ps[v][c] - w + cost;
				if (cost1 < dp[u]) {
					dp[u] = cost1;
					pq.push({-dp[u], u, 0});
				}
			}
		} else {
			if (dp[v] != cost) continue;
			for (auto& E : adj[v]) {
				for (auto& [u, c, w] : E.second) {
					ll cost1 = ps[v][c] - w + cost;
					if (cost1 < dp[u]) {
						dp[u] = cost1;
						pq.push({-dp[u], u, 0});
					}
					ll cost2 = w + cost;
					if (cost2 < dp[u]) {
						dp[u] = cost2;
						pq.push({-dp[u], u, 0});
					}
					ll cost3 = cost;
					if (!dp2[u].count(c) ||  cost3 < dp2[u][c]) {
						dp2[u][c] = cost3;
						pq.push({-dp2[u][c], u, c});
					}
				}
			}
		}
	}
	cout << (dp[n] == (ll)1e18 ? -1 : dp[n]) << "\n";
}

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