Submission #916320

#	Time	Username	Problem	Language	Result	Execution time	Memory
916320		EJIC_B_KEDAX	Robot (JOI21_ho_t4)	C++17	100 / 100	388 ms	45648 KiB

Main

#include <bits/stdc++.h>

#define x first
#define y second

using ll = long long;

using namespace std;

struct triple {
	int x, y;
	ll z;
};

struct four {
	int x, y;
	ll z, t;
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<four>> g(n);
	vector<vector<triple>> g1(n);
	for (int i = 0; i < m; i++) {
		int u, v, c;
		ll p;
		cin >> u >> v >> c >> p; u--; v--; c--;
		g1[u].push_back({v, c, p});
		g1[v].push_back({u, c, p});
	}
	vector<int> cnt(m, 0);
	vector<ll> sum(m, 0);
	for (int i = 0; i < n; i++) {
		for (auto [u, c, p] : g1[i]) {
			cnt[c]++;
			sum[c] += p;
		}
		for (auto [u, c, p] : g1[i]) {
			if (cnt[c] > 1) {
				g[i].push_back({u, c, p, sum[c] - p});
			} else {
				g[i].push_back({u, c, p, 0});
			}
		}
		for (auto [u, c, p] : g1[i]) {
			cnt[c]--;
			sum[c] -= p;
		}
	}
	set<pair<ll, int>> st;
	vector<ll> dist(n, INT64_MAX / 2), dist2(m, INT64_MAX / 2);
	vector<int> used(n, 0);
	dist[0] = 0;
	for (int i = 0; i < n; i++) {
		st.emplace(dist[i], i);
	}
	while (!st.empty()) {
		auto [d, s] = *st.begin();
		st.erase(st.begin());
		for (auto [i, c, p, w] : g[s]) {
			if (used[i]) {
				dist2[c] = min(dist[i], dist2[c]);
			}
		}
		used[s] = 1;
		for (auto [i, c, p, w] : g[s]) {
			if (!used[i]) {
				st.erase({dist[i], i});
				dist[i] = min(dist[i], min({d + w, dist2[c] + w, d + p}));
				st.emplace(dist[i], i);
			}
		}
		for (auto [i, c, p, w] : g[s]) {
			if (used[i]) {
				dist2[c] = INT64_MAX / 2;
			}
		}
	}
	if (dist[n - 1] == INT64_MAX / 2) {
		cout << "-1\n";
	} else {
		cout << dist[n - 1] << "\n";
	}
}

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