Submission #728711

#	Time	Username	Problem	Language	Result	Execution time	Memory
728711		beaboss	Robot (JOI21_ho_t4)	C++14	0 / 100	3080 ms	331832 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;
	}

	vector<map<ll, ll> > dp(n);

	priority_queue<pair<pii, pii> > q; // dist, cur, prev, color, cost

	q.push({{-1, 0}, {-1, -1}});
	ll ans = INF;
	while (!q.empty()) {
		ll d, cur, c, cost;
		d=q.top().f.f;
		cur = q.top().f.s;
		c = q.top().s.f;
		cost=q.top().s.s;
		q.pop();

		if (dp[cur][c] > 0) continue;

		dp[cur][c] = -d;


		// cout << cur << c << -d << endl;

		if (cur == n-1) ans = min(ans, dp[cur][c]);

		for (auto val: adj[cur]) {
			// move along an edge not with color c
			if (val.s.f != c) {
				if (cntadj[cur][val.s.f] != 1) q.push({{-(dp[cur][c] + val.s.s), val.f}, {val.s.f, val.s.s}}); // color edge out
				else q.push({{-(dp[cur][c]), val.f}, {-1, -1}});
				q.push({{-(dp[cur][c] + costadj[cur][val.s.f]), val.f}, {-1, -1}}); // color all in
			} else {
				if (cntadj[cur][val.s.f] != 2) {
					// assert(cntadj[cur][val.s.f] != 1);
					q.push({{-(dp[cur][c] + val.s.s), val.f}, {val.s.f, val.s.s}}); // color edge out
				} else q.push({{-(dp[cur][c]), val.f}, {-1, -1}}); // color edge out
				q.push({{-(dp[cur][c] + costadj[cur][val.s.f] - cost), val.f}, {-1, -1}}); // color all in
			}

		}


	}

	cout << ((ans >= INF) ? -1 : ans-1) << endl;

	



	









	
}

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