Submission #949384

#	Time	Username	Problem	Language	Result	Execution time	Memory
949384		IBory	Robot (JOI21_ho_t4)	C++17	100 / 100	533 ms	94508 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];
map<int, vector<pii>> CS[MAX];
ll D[MAX], C[MAX], P[MAX];

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

	for (int i = 1; i <= N; ++i) {
		for (auto& [c, v] : CS[i]) {
			sort(v.begin(), v.end(), greater<pii>());
			ll all = 0;
			for (auto [s, next] : v) all += s;
			for (auto [s, next] : v) G[i].emplace_back(next, all - s);
			for (int a = 0; a < v.size(); ++a) {
				for (int b = 0; b < min(3, (int)v.size()); ++b) {
					if (a == b) continue;
					// a 바꾸고, b를 complement로 이동
					G[v[a].second].emplace_back(v[b].second, v[a].first + (all - v[a].first - v[b].first));
				}
			}
		}
	}

	memset(D, 0x3f, sizeof(D));
	D[1] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	PQ.emplace(D[1] = 0, 1);
	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		if (cd > D[cur]) continue;
		for (auto [next, nd] : G[cur]) {
			assert(nd >= 0);
			if (D[next] <= cd + nd) continue;
			PQ.emplace(D[next] = cd + nd, next);
		}
	}

	ll ans = (D[N] > 1E18 ? -1 : D[N]);
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for (int a = 0; a < v.size(); ++a) {
      |                    ~~^~~~~~~~~~

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