Submission #728604

#	Time	Username	Problem	Language	Result	Execution time	Memory
728604		beaboss	Robot (JOI21_ho_t4)	C++14	24 / 100	630 ms	47652 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 1e17 + 10ll;

int main() {
	
	ll n, m;
	cin >> n >> m;

	vector<vector<pair<ll, pii> > > adj(n);
	vector<map<ll, ll> > cntadj(n);
	vector<set<ll> > cntin(n);
	vector<ll> dist(n, INF);

	for (ll i = 0; i < m; i++) {
		ll a, b, c, p;
		cin >> a >> b >> c >> p;
		a--;b--;

		adj[a].pb({b, {c, p}});
		adj[b].pb({a, {c, p}});
		cntadj[a][c]++;
		cntadj[b][c]++;
	}

	priority_queue<pair<ll, pii> > q; // dist, node, edge color

	q.push({0, {0, -1}});

	while (!q.empty()) {
		ll cur = q.top().s.f;
		ll d = -q.top().f;
		ll cur_col = q.top().s.s;
		q.pop();

		if (d >= dist[cur]) continue;

		assert(dist[cur]==INF);

		if (cur_col != -1) cntin[cur].insert(cur_col);

		dist[cur]=d;

		while (!q.empty() && q.top().s.f == cur && -q.top().f == dist[cur]) {
			cur = q.top().s.f;
			d = -q.top().f;
			cur_col = q.top().s.s;
			q.pop();

			if (cur_col != -1) cntin[cur].insert(cur_col);
		}
		

		for (auto val: adj[cur]) {
			ll v = val.f;
			ll c = val.s.f;
			ll p = val.s.s;
			if (dist[cur] <= dist[v]) {
				if (cntadj[cur][c] == 1ll) {
					q.push({-(dist[cur]), {v, -1}}); 
				} else if (cntadj[cur][c] == 2ll && cntin[cur].find(c) != cntin[cur].end()) {
					q.push({-(dist[cur]), {v, -1}});
				} else if (dist[cur] + p <= dist[v]) {
					q.push({-(dist[cur] + p), {v, c}});
				}
			}
		}
	}
	if (dist[n-1] >= INF) dist[n-1] = -1;
	cout << dist[n-1] << endl;



	









	
}

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