Submission #1153964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153964		usukhbaatar	Robot (JOI21_ho_t4)	C++20	0 / 100	2229 ms	2162688 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct edge {
	int to, color, cost;
	long long total;

	edge(int _to, int _color, int _cost) {
		to = _to;
		color = _color;
		cost = _cost;
		total = 0;
	}

	bool operator < (const edge& e) const {
		return color < e.color;
	}
};

struct item {
	long long path;
	int from;
	int to;
	int cost;
	int color;

	item(long long _path, int _from, int _to, int _cost, int _color) {
		path = _path;
		from = _from;
		to = _to;
		cost = _cost;
		color = _color;
	}

	bool operator < (const item& a) const {
		return path > a.path;
	}
};

int n, m;
vector<vector<edge>> adj;

int main() {
	cin >> n >> m;
	adj.resize(n);
	for (int i = 0; i < m; i++) {
		int u, v, color, cost;
		cin >> u >> v >> color >> cost;
		u--; v--;
		adj[u].emplace_back(v, color, cost);
		adj[v].emplace_back(u, color, cost);
	}

	for (int u = 0; u < n; u++) {
		vector<edge> &edges = adj[u];
		long long total = 0;
		sort(edges.begin(), edges.end());
		for (int i = 0; i < edges.size(); i++) {
			if (i == 0 || edges[i].color != edges[i - 1].color) {
				total = edges[i].cost;
				for (int j = i + 1; j < edges.size(); j++) {
					if (edges[j].color != edges[i].color) break;
					total += edges[j].cost;
				}
				// cout << u + 1 << ' ' << edges[i].color << ' ' << total << endl;
			}
			edges[i].total = total;

		}
	}

	priority_queue<item> q;
	//(long long _path, int _from, int _to, int _cost, int _color)
	q.emplace(0, -1, 0, 0, 0);
	// q.emplace(0, -1, 1, 0, 0);
	// vector<bool> vis(2 * n + 2, 0);
	set<pair<int, int>> vis;
	int ans = -1;
	while (!q.empty()) {
		item curr = q.top(); q.pop();
		int u1 = curr.to;
		
		int path = curr.path;
		int p = curr.from;
		int from_cost = curr.cost;
		int from_color = curr.color;
		int u = u1 / 2;
		// printf("%d to %d: %d\n", p, u1, path);
		// cout << u + 1 << " "<< u1 << " " << path << endl;
		if (vis.find({p, u1}) != vis.end()) continue;
		vis.insert({p, u1});
		// if (vis[u1]) continue;
		// vis[u1] = 1;
		// cout << p << " to " << u + 1 << () << " dist: " << path << endl;
		if (u == n - 1) { ans = path; break; }
		for (edge &e : adj[u]) {
			int v = e.to;
			int to_color = e.color;
			int to_cost = e.cost;
			long long total = e.total;

			int v1 = 2 * v;
			// if (!vis[v1]) {
				// real
				int cost = total - to_cost;
				if (u1 & 1) {
					if (from_color == to_color) cost -= from_cost;
					q.emplace(path + cost, u1, v1, cost, to_color);
				} else { // real to real: real
					if (from_color != to_color) {
						q.emplace(path + cost, u1, v1, cost, to_color);
					}
				}
			// }

			int v2 = 2 * v + 1;
			// if (!vis[v2]) {
				// fake
				// if (v2 == 23) cout << "::: " << to_cost << "L " << path + to_cost << endl;
				q.emplace(path + to_cost, u1, v2, to_cost, to_color);
			// }
		}
	}
	cout << ans << endl;
	return 0;
}

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