Submission #771053

#	Time	Username	Problem	Language	Result	Execution time	Memory
771053		SamNguyen	Robot (JOI21_ho_t4)	C++14	0 / 100	3043 ms	28168 KiB

Main

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

template <class T> 
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const lli INF = 0x1f1f1f1f1f1f1f1f;
const int MAX_N = 1e5 + 7;
const int MAX_M = 2e5 + 7;

template <class T1, class T2>
inline constexpr bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

class Edge {
private:
	int u, v, c;
	lli w;

public:
	Edge(int u = 0, int v = 0, int c = 0, lli w = 0): u(u), v(v), c(c), w(w) {}

	inline lli cost() const { return w; }
	inline pair<int, int> nodes() const { return make_pair(u, v); }
	inline int other_node(int z) const { return u ^ v ^ z; }
	inline int colour() const { return c; }

	inline int get_node(bool is_rev) const { return is_rev ? v : u; }
	inline bool is_start(int z) const { return z == u; }
};

int N, M;
Edge edge[MAX_M];
vector<int> adj[MAX_N];

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v, c; lli w;
		cin >> u >> v >> c >> w;
		edge[i] = Edge(u, v, c, w);
		adj[u].push_back(i);
		adj[v].push_back(i);
	}

	edge[M] = Edge(0, 1, M + 1, 0);
}

lli dist[MAX_M][2][2];
min_priority_queue<tuple<lli, int, bool, bool>> pq;
int cnt_colour[MAX_M];

lli solve() {
	memset(dist, 0x1f, sizeof dist);
	memset(cnt_colour, 0, sizeof cnt_colour);

	auto relax = [&](int i, bool is_rev, bool is_prev_mod, lli d) {
		if (minimise(dist[i][is_rev][is_prev_mod], d))
			pq.emplace(d, i, is_rev, is_prev_mod);
	};

	relax(M, 0, 0, 0);

	lli ans = INF;
	while (not pq.empty()) {
		lli cur_dist; int i; bool is_rev, is_prev_mod;
		tie(cur_dist, i, is_rev, is_prev_mod) = pq.top();
		pq.pop();

		{
			int u, v;
			tie(u, v) = edge[i].nodes();
			if (is_rev)
				swap(u, v);

			cerr << "edge (" << u << "," << v << "), is_prev_mod = " << is_prev_mod << " ==> " << cur_dist << endl;
		}

		int v = edge[i].get_node(not is_rev);
		if (v == N) 
			minimise(ans, cur_dist);

		for (int j : adj[v]) {
			int c = edge[j].colour();
			cerr << j << "(" << c << ") ";

			if (j == i and not is_prev_mod)
				continue;

			cnt_colour[c]++;
		}
		cerr << endl;

		for (int j : adj[v]) {
			int c = edge[j].colour();
			if (cnt_colour[c] <= 1)
				relax(j, not edge[j].is_start(v), false, cur_dist);

			relax(j, not edge[j].is_start(v), true, cur_dist + edge[j].cost());
		}

		for (int j : adj[v]) {
			int c = edge[j].colour();
			cnt_colour[c] = 0;
		}
	}

	if (ans >= INF)
		ans = -1;
	return ans;
}

int main(void) {
	input();
	cout << solve();

	return 0;
}

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