Submission #684855

#	Time	Username	Problem	Language	Result	Execution time	Memory
684855		NK_	Robot (JOI21_ho_t4)	C++17	100 / 100	540 ms	51284 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define mp make_pair
#define f first
#define s second

using pi = pair<int, int>;
using ll = long long;

using T = array<ll, 3>;

const ll INFL = ll(1e18) + 1008;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	vector<int> C(M), U(M), V(M); vector<ll> P(M);
	vector<vector<vector<pi>>> adj(N);
	vector<vector<int>> co(N, {-1});

	for(int i = 0; i < M; i++) {
		cin >> U[i] >> V[i] >> C[i] >> P[i]; --U[i], --V[i], --C[i];
		co[U[i]].push_back(C[i]);
		co[V[i]].push_back(C[i]);
	}

	vector<vector<ll>> dst(N);
	vector<vector<bool>> vis(N);
	for(int u = 0; u < N; u++) {
		sort(begin(co[u]), end(co[u]));
		co[u].erase(unique(begin(co[u]), end(co[u])), end(co[u]));
		dst[u].assign(size(co[u]) + 1, INFL);
		vis[u].assign(size(co[u]) + 1, 0);
		adj[u].assign(size(co[u]) + 1, {});
	}

	auto get = [&](int x, int c) { return lower_bound(begin(co[x]), end(co[x]), c) - begin(co[x]); };

	for(int i = 0; i < M; i++) {
		adj[U[i]][get(U[i], C[i])].push_back(mp(V[i], i));
		adj[V[i]][get(V[i], C[i])].push_back(mp(U[i], i));
	}


	priority_queue<T, vector<T>, greater<T>> q; 
	q.push({dst[0][0] = 0, 0, -1});


	while(size(q) > 0) {
		auto [d, u, c] = q.top(); q.pop();

		int CO = (c == -1 ? 0 : get(u, c));
		if (vis[u][CO]) continue;
		vis[u][CO] = 1;

		if (CO == 0) {
			for(int x = 1; x < int(size(co[u])); x++) {
				ll S = 0;
				for(auto e : adj[u][x]) S += P[e.s];
				
				for(auto e : adj[u][x]) {
					int v, i; tie(v, i) = e;
					int cv = get(v, co[u][x]);
					ll w = min(S - P[i], P[i]);

					if (dst[v][cv] > dst[u][CO]) q.push({dst[v][cv] = dst[u][CO], v, co[u][x]});
					if (dst[v][0] > (dst[u][CO]+w)) q.push({dst[v][0] = (dst[u][CO]+w), v, -1});
				} 
			}
		} else {

			ll S = 0;
			for(auto e : adj[u][CO]) S += P[e.s];

			for(auto e : adj[u][CO]) {
				int v, i; tie(v, i) = e;
				ll w = S - P[i];

				if (dst[v][0] > (dst[u][CO]+w)) q.push({dst[v][0] = (dst[u][CO]+w), v, -1});
			}
		}
	}


	cout << (dst[N-1][0] == INFL ? -1 : dst[N-1][0]) << nl;
	
    return 0;
}

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