Submission #728609

#	Time	Username	Problem	Language	Result	Execution time	Memory
728609		beaboss	Robot (JOI21_ho_t4)	C++14	24 / 100	573 ms	47932 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}});

	vector<int> todo;
	int prev = 0;
	while (!q.empty() || !todo.empty()) {
		if (q.empty() || prev < -q.top().f) {
			for (auto cur: todo) {
				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}});
						}
					}
				}
			}
			todo.erase(todo.begin(), todo.end());
		}
		if (q.empty()) break;
		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);
		}

		todo.push_back(cur);
		prev = dist[cur];



		

		
	}
	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