Submission #476898

#	Time	Username	Problem	Language	Result	Execution time	Memory
476898		NinjaDoggy	Robot (JOI21_ho_t4)	C++17	34 / 100	3082 ms	80076 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 edgeCosts[MAX_M];
int N, M;
vector <Edge> adj[MAX_N];
unordered_map<int, ll> adjColors[MAX_N];
unordered_map<ll, ll> dp;

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] += p;
		adj[b].push_back(*new Edge(i, a, c, p));
		adjColors[b][c] += p;
		edgeColors[i] = c;
		edgeCosts[i] = p;
	}
	add(0, -1, 0, 0);
	ll ans = oo;
	while (!pq.empty()) {
		State cur = pq.top();
		pq.pop();
		ll key = 0;
		key += cur.node;
		key *= MAX_M;
		key += 1 + cur.prevEdge;
		key *= 2;
		key += cur.recolored;
		if (dp[key] < cur.dist)continue;
		if (cur.node == N - 1) {
			ans = min(ans, cur.dist);
		}
		for (Edge& e : adj[cur.node]) {
			if (e.id == cur.prevEdge)continue;
			ll colorCost = adjColors[cur.node][e.color];
			colorCost -= e.cost;
			if (cur.recolored && edgeColors[cur.prevEdge] == e.color) {
				colorCost -= edgeCosts[cur.prevEdge];
			}
			add(e.nextNode, e.id, false, cur.dist + colorCost);
			add(e.nextNode, e.id, true, cur.dist + e.cost);
		}
	}
	if (ans == oo)ans = -1;
	cout << ans;
}

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