제출 #791385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791385		IBory	Robot (JOI21_ho_t4)	C++17	0 / 100	3051 ms	14736 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);
		}
	}
	// cout << col << ' ' << D[N] << '\n';
	return D[N];
}

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 = -1;
	for (int c : col) ans = max(ans, Dijkstra(c, N));

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

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