Submission #794705

#	Time	Username	Problem	Language	Result	Execution time	Memory
794705		IBory	Robot (JOI21_ho_t4)	C++17	34 / 100	3082 ms	138848 KiB

Main

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 300007;
vector<pii> G[MAX];
map<int, ll> CS[MAX];
map<ll, ll> D[MAX][2];
ll P[MAX], C[MAX];

ll Dijkstra(int N) {
	priority_queue<pair<ll, tuple<ll, ll, ll>>, vector<pair<ll, tuple<ll, ll, ll>>>, greater<pair<ll, tuple<ll, ll, ll>>>> PQ;
	PQ.emplace(D[1][0][0] = 0, make_tuple(1, 0, 0));

	while (!PQ.empty()) {
		auto [cd, p] = PQ.top(); PQ.pop();
		ll cur, pen, change;
		tie(cur, change, pen) = p;
		if (cur == N) return cd;
		if (cd > D[cur][change][pen]) continue;
		for (auto [next, en] : G[cur]) {
			ll c0 = CS[cur][C[en]] - P[en] - (change && C[pen] == C[en] ? P[pen] : 0LL);
			ll c1 = P[en];
			if (cd + c0 < D[next][0][en]) {
				PQ.emplace(D[next][0][en] = cd + c0, make_tuple(next, 0, en));
			}
			if (cd + c1 < D[next][1][en]) {
				PQ.emplace(D[next][1][en] = cd + c1, make_tuple(next, 1, en));
			}
		}
	}

	return -1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		ll a, b;
		cin >> a >> b >> C[i] >> P[i];
		G[a].emplace_back(b, i);
		G[b].emplace_back(a, i);
	}

	for (int i = 1; i <= N; ++i) {
		for (auto [_, en] : G[i]) {
			CS[i][C[en]] += P[en];
			D[i][0][en] = D[i][1][en] = 1e18;
		}
	}

	cout << Dijkstra(N);
	return 0;
}

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