Submission #794702

#	Time	Username	Problem	Language	Result	Execution time	Memory
794702		IBory	Robot (JOI21_ho_t4)	C++17	34 / 100	143 ms	63960 KiB

Main

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

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

ll Dijkstra(int N) {
	memset(D, 0x3f, sizeof(D));
	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, pen, change) = p;
		if (cur == N) return cd;
		if (cd > D[cur][pen][change]) 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][en][0]) {
				PQ.emplace(D[next][en][0] = cd + c0, make_tuple(next, en, 0));
			}
			if (cd + c1 < D[next][en][1]) {
				PQ.emplace(D[next][en][1] = cd + c1, make_tuple(next, en, 1));
			}
		}
	}

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

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

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