oj.uz

Submission #916310

# Submission time Handle Problem Language Result Execution time Memory
916310 2024-01-25T16:03:17 Z EJIC_B_KEDAX Robot (JOI21_ho_t4) C++17
0 / 100
 171 ms 26704 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 26704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -