Submission #476895

#	Time	Username	Problem	Language	Result	Execution time	Memory
476895		NinjaDoggy	Robot (JOI21_ho_t4)	C++17	0 / 100	3076 ms	74112 KiB

Main

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

#define FOR(i, N) for (int i = 0; i < N; i++)
#define ll long long

const int MAX_N = 1e5 + 5;
const int MAX_M = 2e5 + 5;
const ll oo = 1LL << 60;

struct Edge {
	int id;
	int nextNode;
	int color;
	int cost;
	Edge(int i, int b, int c, int p) {
		id = i;
		nextNode = b;
		color = c;
		cost = p;
	}
};

int edgeColors[MAX_M];
int N, M;
vector <Edge> adj[MAX_N];
unordered_map<int, int> adjColors[MAX_N];
unordered_map<ll, ll> dp;

ll solve(int node, int prevEdge, bool recolored) {
	if (node == N - 1) {
		return 0;
	}
	ll key = 0;
	key += node;
	key *= MAX_M;
	key += 1 + prevEdge;
	key *= 2;
	key += recolored;

	if (dp.find(key) != dp.end()) {
		return dp[key];
	}
	ll ans = oo;
	for (Edge& e : adj[node]) {
		if (e.id == prevEdge)continue;
		int colorCount = adjColors[node][e.color];
		if (recolored && edgeColors[prevEdge] == e.color) {
			colorCount--;
		}
		if (colorCount == 1) {
			ans = min(ans, solve(e.nextNode, e.id, false));
		}
		else {
			ans = min(ans, solve(e.nextNode, e.id, true) + e.cost);
		}
	}

	dp[key] = ans;
	return ans;
}
struct State {
	int node, prevEdge;
	bool recolored;
	ll dist;
	State(int n, int p, bool r, ll c) {
		node = n;
		prevEdge = p;
		recolored = r;
		dist = c;
	}
};
struct Compare {
	bool operator() (State& a, State& b) {
		return a.dist > b.dist;
	}
};
priority_queue<State, std::vector<State>, Compare> pq;
inline void add(int node, int prevEdge, bool recolored, ll dist) {
	ll key = 0;
	key += node;
	key *= MAX_M;
	key += 1 + prevEdge;
	key *= 2;
	key += recolored;
	if (dp.find(key) == dp.end() || dp[key] > dist) {
		dp[key] = dist;
		pq.push(*new State(node, prevEdge, recolored, dist));
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	FOR(i, M) {
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		a--;
		b--;
		adj[a].push_back(*new Edge(i, b, c, p));
		adjColors[a][c]++;
		adj[b].push_back(*new Edge(i, a, c, p));
		adjColors[b][c]++;
		edgeColors[i] = c;
	}
	//ll ans = solve(0, -1, 0);
	//if (ans >= oo) {
	//	ans = -1;
	//}
	//cout << ans;
	pq.push(*new State(0, -1, 0, 0));
	while (!pq.empty()) {
		State cur = pq.top();
		pq.pop();
		if (cur.node == N - 1) {
			cout << cur.dist << "\n";
			return 0;
		}
		ll key = 0;
		key += cur.node;
		key *= MAX_M;
		key += 1 + cur.prevEdge;
		key *= 2;
		key += cur.recolored;
		if (dp[key] < cur.dist)continue;
		for (Edge& e : adj[cur.node]) {
			if (e.id == cur.prevEdge)continue;
			int colorCount = adjColors[cur.node][e.color];
			if (cur.recolored && edgeColors[cur.prevEdge] == e.color) {
				colorCount--;
			}
			if (colorCount == 1) {
				add(e.nextNode, e.id, false, cur.dist);
			}
			else {
				add(e.nextNode, e.id, true, cur.dist + e.cost);
			}
		}
	}
	cout << -1;
}

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