Submission #916310

#	Time	Username	Problem	Language	Result	Execution time	Memory
916310		EJIC_B_KEDAX	Robot (JOI21_ho_t4)	C++17	0 / 100	171 ms	26704 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;
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, ll>>> 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].emplace_back(u, min(p, sum[c] - p));
			} else {
				g[i].emplace_back(u, 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);
	vector<int> used(n, 0);
	dist[0] = 0;
	for (int i = 0; i < n; i++) {
		st.emplace(i, dist[i]);
	}
	while (!st.empty()) {
		auto [d, s] = *st.begin();
		st.erase(st.begin());
		used[s] = 1;
		for (auto [i, w] : g[s]) {
			if (!used[i]) {
				st.erase({dist[i], i});
				dist[i] = min(dist[i], d + w);
				st.emplace(dist[i], i);
			}
		}
	}
	if (dist[n - 1] == INT64_MAX / 2) {
		cout << "-1\n";
	} else {
		cout << dist[n - 1] << "\n";
	}
}

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