Submission #1219565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219565		trimkus	Robot (JOI21_ho_t4)	C++20	0 / 100	70 ms	53696 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN = 4e5;

vector<array<int, 3>> edges[MAXN + 1];
vector<array<ll, 2>> adj[MAXN + 1];

void add_edge(int s, int e, ll w) {
	adj[s].push_back({e, w});
}

vector<array<int, 2>> out[MAXN + 1];
vector<int> in[MAXN + 1];
ll costOut[MAXN + 1];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int idx = n;
	for (int i = 0; i < m; ++i) {
		int a, b, c, w;
		cin >> a >> b >> c >> w;
		edges[c].push_back({a, b, w});
		edges[c].push_back({b, a, w});
	}
	for (int i = 1; i <= m; ++i) {
		for (auto& [s, e, w] : edges[i]) {
			in[e].push_back(s);
			out[s].push_back({e, w});
			costOut[s] += w;
		}
		for (auto& [s, e, w] : edges[i]) {
			add_edge(s, e, min(1LL * w, 1LL * costOut[s] - w));
			if ((int)out[s].size() > 0) {
				idx += 1;
				for (auto& [e, w] : out[s]) {
					add_edge(idx, e, costOut[s] - w);
				}
				for (auto& e : in[s]) {
					add_edge(e, idx, 0); 
				}
				out[s].clear();
			}
		}
		for (auto& [s, e, w] : edges[i]) {
			in[e].clear();
			costOut[s] = 0;
		}
	}
	priority_queue<array<ll, 2>> pq;
	vector<ll> dist(idx + 1, (ll)1e18);
	pq.push({0, 1});
	while (pq.size()) {
		ll cost = -pq.top()[0];
		int v = pq.top()[1];
		pq.pop();
		if (dist[v] != cost) continue;
		//~ cerr << v << " = " << cost << "\n";
		for (auto& [u, w] : adj[v]) {
			if (cost + w < dist[u]) {
				dist[u] = cost + w;
				pq.push({-dist[u], u});
			}
		}
	}
	if (dist[n] > (ll)1e17) dist[n] = -1;
	cout << dist[n] << "\n";
}

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