Submission #791389

#	Time	Username	Problem	Language	Result	Execution time	Memory
791389		IBory	Robot (JOI21_ho_t4)	C++17	0 / 100	3055 ms	13248 KiB

Main

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

const int MAX = 200007;
vector<pii> G[MAX];
ll C[MAX], P[MAX], D[MAX];

ll Dijkstra(int col, int N) {
	memset(D, 0x3f, sizeof(D));
	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	PQ.emplace(D[1] = 0, 1);
	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		for (auto [next, en] : G[cur]) {
			ll nd = (C[en] == col ? 0LL : P[en]);
			if (cd + nd >= D[next]) continue;
			PQ.emplace(D[next] = cd + nd, next);
		}
	}
	ll ret = 0;
	for (int i = 1; i <= N; ++i) ret = max(ret, D[i]);
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> col;
	for (int i = 0; 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);
		col.push_back(C[i]);
	}

	ll ans = 2e18;
	for (int c : col) ans = min(ans, Dijkstra(c, N));

	cout << (ans > 1e18 ? -1LL : ans);
	return 0;
}

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