Submission #728629

#	Time	Username	Problem	Language	Result	Execution time	Memory
728629		beaboss	Robot (JOI21_ho_t4)	C++14	24 / 100	879 ms	70496 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<map<ll, ll> > costadj(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]++;
		costadj[a][c] += p;
		costadj[b][c] += p;
	}

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

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

	vector<ll> todo;
	ll prev = 0;
	while (!q.empty() || !todo.empty()) {
		if (q.empty() || prev < -q.top().f) {
			for (auto cur: todo) {
				// cout << cur << dist[cur] << endl;
				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[cur] + costadj[cur][c]-p <= dist[v]) {
						q.push({-(dist[cur] + costadj[cur][c]-p), {v, -1}});
					}
				}
			}
			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] || (cur_col == -1 && 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];

		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}});
				}
			}
		}

		

		
	}
	if (dist[n-1] >= INF) dist[n-1] = -1;
	cout << dist[n-1] << endl;



	









	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:99:7: warning: unused variable 'p' [-Wunused-variable]
   99 |    ll p = val.s.s;
      |       ^

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