Submission #388882

# Submission time Handle Problem Language Result Execution time Memory
388882 2021-04-13T08:49:47 Z Vlatko Robot (JOI21_ho_t4) C++17
100 / 100
1087 ms 84308 KB
// Note: This solution is from usaco.guide

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

const ll inf = 1e18;
const int N = 100010;

struct Edge {
	int to, c;
	ll p;
};

int n, m;
map<int, vector<Edge>> graph[N]; // graph[node][edge color]
ll dist[N]; // d[node] = distance, entered through an edge that won't be touched again
map<int, ll> dist2[N]; // d2[node][edge color c] = distance, but entered through c, must exit through c by recoloring all adjacent (including the one we entered through)
map<int, ll> psum[N]; // csum[node][edge color] = sum of weights

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b, c, p;
		cin >> a >> b >> c >> p;
		graph[a][c].push_back({b, c, p});
		graph[b][c].push_back({a, c, p});
		psum[a][c] += p;
		psum[b][c] += p;
	}
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
	}
	dist[1] = 0;
	using pqState = tuple<ll, int, int>; // d, u, c (color of back edge)
	priority_queue<pqState, vector<pqState>, greater<pqState>> pq;
	pq.emplace(0, 1, 0);
	while (!pq.empty()) {
		ll dist_node;
		int node, bkc; // node, back color
		tie(dist_node, node, bkc) = pq.top();
		pq.pop();
		if (bkc > 0) {
			// special case: dp2
			if (dist_node != dist2[node][bkc]) continue;
			for (Edge e : graph[node][bkc]) {
				// must exit through same colored edge and flip all others
				ll alt = dist_node + psum[node][bkc] - e.p;
				if (alt < dist[e.to]) {
					dist[e.to] = alt;
					pq.emplace(alt, e.to, 0);
				}
			}
		} else {
			if (dist_node != dist[node]) continue;
			for (auto& kvp : graph[node]) {
				for (Edge e : kvp.second) {
					ll alt;
					// case 1: don't recolor e, recolor all except e
					alt = dist_node + psum[node][e.c] - e.p;
					if (alt < dist[e.to]) {
						dist[e.to] = alt;
						pq.emplace(alt, e.to, 0);
					}
					// case 2: recolor only e and no other
					alt = dist_node + e.p;
					if (alt < dist[e.to]) {
						dist[e.to] = alt;
						pq.emplace(alt, e.to, 0);
					}
					// case 3: don't recolor e NOW, but must recolor all adjacent next node
					alt = dist_node;
					if (!dist2[e.to].count(e.c) || alt < dist2[e.to][e.c]) {
						dist2[e.to][e.c] = alt;
						pq.emplace(alt, e.to, e.c);
					}
				}
			}
		}
	}
	cout << (dist[n] == inf ? -1 : dist[n]) << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14320 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 10 ms 14560 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 13 ms 15052 KB Output is correct
10 Correct 12 ms 14960 KB Output is correct
11 Correct 11 ms 14824 KB Output is correct
12 Correct 11 ms 14664 KB Output is correct
13 Correct 11 ms 14684 KB Output is correct
14 Correct 11 ms 14780 KB Output is correct
15 Correct 10 ms 14688 KB Output is correct
16 Correct 11 ms 14688 KB Output is correct
17 Correct 11 ms 14812 KB Output is correct
18 Correct 12 ms 14540 KB Output is correct
19 Correct 11 ms 14668 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 235 ms 34436 KB Output is correct
2 Correct 97 ms 24632 KB Output is correct
3 Correct 252 ms 31572 KB Output is correct
4 Correct 154 ms 27708 KB Output is correct
5 Correct 1076 ms 82264 KB Output is correct
6 Correct 932 ms 71888 KB Output is correct
7 Correct 404 ms 56340 KB Output is correct
8 Correct 473 ms 50828 KB Output is correct
9 Correct 525 ms 50908 KB Output is correct
10 Correct 375 ms 47860 KB Output is correct
11 Correct 164 ms 32672 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14320 KB Output is correct
5 Correct 9 ms 14412 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 10 ms 14560 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Correct 13 ms 15052 KB Output is correct
10 Correct 12 ms 14960 KB Output is correct
11 Correct 11 ms 14824 KB Output is correct
12 Correct 11 ms 14664 KB Output is correct
13 Correct 11 ms 14684 KB Output is correct
14 Correct 11 ms 14780 KB Output is correct
15 Correct 10 ms 14688 KB Output is correct
16 Correct 11 ms 14688 KB Output is correct
17 Correct 11 ms 14812 KB Output is correct
18 Correct 12 ms 14540 KB Output is correct
19 Correct 11 ms 14668 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
21 Correct 235 ms 34436 KB Output is correct
22 Correct 97 ms 24632 KB Output is correct
23 Correct 252 ms 31572 KB Output is correct
24 Correct 154 ms 27708 KB Output is correct
25 Correct 1076 ms 82264 KB Output is correct
26 Correct 932 ms 71888 KB Output is correct
27 Correct 404 ms 56340 KB Output is correct
28 Correct 473 ms 50828 KB Output is correct
29 Correct 525 ms 50908 KB Output is correct
30 Correct 375 ms 47860 KB Output is correct
31 Correct 164 ms 32672 KB Output is correct
32 Correct 162 ms 28380 KB Output is correct
33 Correct 197 ms 29216 KB Output is correct
34 Correct 458 ms 50096 KB Output is correct
35 Correct 351 ms 41508 KB Output is correct
36 Correct 388 ms 46892 KB Output is correct
37 Correct 419 ms 49252 KB Output is correct
38 Correct 397 ms 55668 KB Output is correct
39 Correct 190 ms 31840 KB Output is correct
40 Correct 490 ms 52192 KB Output is correct
41 Correct 530 ms 52236 KB Output is correct
42 Correct 571 ms 60988 KB Output is correct
43 Correct 250 ms 36916 KB Output is correct
44 Correct 513 ms 42740 KB Output is correct
45 Correct 367 ms 47556 KB Output is correct
46 Correct 323 ms 47944 KB Output is correct
47 Correct 365 ms 49180 KB Output is correct
48 Correct 1087 ms 84308 KB Output is correct