Submission #1153317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153317		usukhbaatar	Robot (JOI21_ho_t4)	C++20	0 / 100	209 ms	26468 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;
				}
			}
			edges[i].total = total;
		}
	}

	priority_queue<item> q;
	q.emplace(0, -1, 0, 0, 0);
	q.emplace(0, -1, 0, 1, 0);
	vector<bool> vis(2 * n + 2, 0);
	int ans = -1;
	while (!q.empty()) {
		item curr = q.top(); q.pop();
		int u1 = curr.to;
		if (vis[u1]) continue;
		vis[u1] = 1;
		int path = curr.path;
		int p = curr.from;
		int from_cost = curr.cost;
		int from_color = curr.color;
		int u = u1 / 2;
		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]) {
				// fake to real: real
				if (u1 & 1) {
					int cost = total - to_cost;
					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) {
						int cost = total - to_cost;
						q.emplace(path + cost, u1, v1, cost, to_color);
					}
				}
			}

			int v2 = 2 * v + 1;
			if (!vis[v2]) {
				// to fake: fake
				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