Submission #1097324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097324		nrg_studio	Robot (JOI21_ho_t4)	C++17	34 / 100	3040 ms	66748 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define chmin(a, b) a = min(a,b)
#define chmax(a,b) a = max(a,b)

using T = pair<ll,pii>;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m, a, b, c, p; cin >> n >> m;
	vector<map<int,ll>> trsn(n), sum(n);
	vector<ll> dist(n,LLONG_MAX); // self, complement
	vector<vector<T>> adj(n);
	F0R(i,m) {
		cin >> a >> b >> c >> p; a--; b--;
		adj[a].pb({b,{c,p}});
		adj[b].pb({a,{c,p}});
		trsn[a][c] = trsn[b][c] = LLONG_MAX;
		sum[a][c] += p; sum[b][c] += p;
	}
	priority_queue<T,vector<T>,greater<T>> pq; // dist, node, color [1,m], 0 for unspecified color
	// t->c, c->c, s->s, c->s->t
	dist[0] = 0; 
	pq.push({0,{0,0}});
	//for(auto& x : trsn[0]) {x.s = 0; pq.push({0,{0,x.f}});}

	while (pq.size()) {
		auto[d,z] = pq.top(); pq.pop();
		auto[cur,t] = z;

		if ((!t && dist[cur]!=d) || (t && trsn[cur][t]!=d)) {continue;}

		/*
		self->complement is to any colors such that they are not the 
		color you came from, but you don't care because if you transition to 
		the same color you get an unoptimal answer that you will rectify
		with transition->complement
		so self and complement push to the same thing, so combine them
		*/
		for (T z : adj[cur]) {
			auto[x,y] = z; auto[c,p] = y;
			if (!t) { // push to (self, complement), and transition
				if (d+p<dist[x]) {pq.push({dist[x]=d+p,{x,0}});}
				if (d+sum[cur][c]-p<dist[x]) {pq.push({dist[x]=d+sum[cur][c]-p,{x,0}});}
				if (d<trsn[x][c]) {pq.push({trsn[x][c]=d,{x,c}});}
				//cout<<dist[2]<<'\n';
			} else if (t==c) { // push to complement
				//cout << sum[cur][c]-p << '\n';
				//cout << x+1 << " " << c << '\n';
				if (sum[cur][c]+d-p<dist[x]) {pq.push({dist[x]=sum[cur][c]+d-p,{x,0}});}
			}
		}
	} cout << (dist[n-1]==LLONG_MAX ? -1 : dist[n-1]) << '\n';
	//cout<<dist[3]<<'\n';
}

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