Submission #490139

# Submission time Handle Problem Language Result Execution time Memory
490139 2021-11-25T21:04:33 Z rainliofficial Robot (JOI21_ho_t4) C++17
100 / 100
698 ms 79144 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


struct Edge{
	int to, c, p, id;
};
struct State{
	int node, prevEdge, colorLater;
	ll cost;
};
bool cmp(const State& a, const State& b){
	return a.cost > b.cost;
}

const ll INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5;
int n, m;
map<int, vector<Edge>> arr[MAXN];
map<int, ll> recolor[MAXN];
ll dp[MAXN];
int edge_color[MAXM], edge_cost[MAXM];
map<int, ll> dp2[MAXN];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	cin >> n >> m;
	for (int i=0; i<m; i++){
		int s, e, c, p;
		cin >> s >> e >> c >> p;
		s--; e--;
		recolor[s][c] += p;
		recolor[e][c] += p;
		arr[s][c].push_back({e, c, p, i});
		arr[e][c].push_back({s, c, p, i});
		edge_color[i] = c;
		edge_cost[i] = p;
	}
	for (int i=0; i<n; i++){
		dp[i] = INF;
	}
	priority_queue<State, vector<State>, decltype(&cmp)> pq(cmp);
	pq.push({0, -1, 0, 0});
	dp[0] = 0;
	while (!pq.empty()){
		State curr = pq.top();
		pq.pop();
		// cout << curr.cost << "\n";
		if (curr.colorLater == 1){
			if (dp2[curr.node][edge_color[curr.prevEdge]] != curr.cost){
				continue;
			}
			for (Edge e : arr[curr.node][edge_color[curr.prevEdge]]){
				if (e.id == curr.prevEdge){
                    continue;
                }
                ll nc = curr.cost + recolor[curr.node][e.c] - e.p;
                if (nc < dp[e.to]){
                    pq.push({e.to, e.id, 0, nc});
                    dp[e.to] = nc;
                }
			}
		}else{
			if (dp[curr.node] != curr.cost){
				continue;
			}
			for (auto& s : arr[curr.node]){
				for (Edge e : s.second){
					if (e.id == curr.prevEdge){
						continue;
					}
					// Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
                    ll case1 = curr.cost + e.p;
                    if (case1 < dp[e.to]){
                        dp[e.to] = case1;
                        pq.push({e.to, e.id, 0, case1});
                    }   
                    // Recolor all other edges
                    ll case2 = curr.cost + recolor[curr.node][e.c] - e.p;
                    if (case2 < dp[e.to]){
                        dp[e.to] = case2;
                        pq.push({e.to, e.id, 0, case2});
                    }
                    // Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
                    // to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
                    ll case3 = curr.cost;
                    if (!dp2[e.to].count(e.c) || case3 < dp2[e.to][e.c]){
                        dp2[e.to][e.c] = case3;
                        pq.push({e.to, e.id, 1, case3});
                    }
				}
			}
		}
	}
	ll ans = dp[n-1];
	if (ans == INF) ans = -1;
	cout << ans << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14596 KB Output is correct
8 Correct 8 ms 14384 KB Output is correct
9 Correct 10 ms 15052 KB Output is correct
10 Correct 9 ms 14924 KB Output is correct
11 Correct 8 ms 14796 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 9 ms 14796 KB Output is correct
14 Correct 12 ms 14796 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 9 ms 14764 KB Output is correct
17 Correct 9 ms 14772 KB Output is correct
18 Correct 8 ms 14540 KB Output is correct
19 Correct 12 ms 14676 KB Output is correct
20 Correct 10 ms 14668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 173 ms 33388 KB Output is correct
2 Correct 65 ms 23944 KB Output is correct
3 Correct 171 ms 30304 KB Output is correct
4 Correct 99 ms 27052 KB Output is correct
5 Correct 698 ms 79144 KB Output is correct
6 Correct 550 ms 68844 KB Output is correct
7 Correct 281 ms 51212 KB Output is correct
8 Correct 349 ms 48356 KB Output is correct
9 Correct 358 ms 48280 KB Output is correct
10 Correct 267 ms 45772 KB Output is correct
11 Correct 113 ms 31684 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 10 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14596 KB Output is correct
8 Correct 8 ms 14384 KB Output is correct
9 Correct 10 ms 15052 KB Output is correct
10 Correct 9 ms 14924 KB Output is correct
11 Correct 8 ms 14796 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 9 ms 14796 KB Output is correct
14 Correct 12 ms 14796 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 9 ms 14764 KB Output is correct
17 Correct 9 ms 14772 KB Output is correct
18 Correct 8 ms 14540 KB Output is correct
19 Correct 12 ms 14676 KB Output is correct
20 Correct 10 ms 14668 KB Output is correct
21 Correct 173 ms 33388 KB Output is correct
22 Correct 65 ms 23944 KB Output is correct
23 Correct 171 ms 30304 KB Output is correct
24 Correct 99 ms 27052 KB Output is correct
25 Correct 698 ms 79144 KB Output is correct
26 Correct 550 ms 68844 KB Output is correct
27 Correct 281 ms 51212 KB Output is correct
28 Correct 349 ms 48356 KB Output is correct
29 Correct 358 ms 48280 KB Output is correct
30 Correct 267 ms 45772 KB Output is correct
31 Correct 113 ms 31684 KB Output is correct
32 Correct 111 ms 26132 KB Output is correct
33 Correct 136 ms 28216 KB Output is correct
34 Correct 351 ms 47144 KB Output is correct
35 Correct 259 ms 39216 KB Output is correct
36 Correct 253 ms 45052 KB Output is correct
37 Correct 305 ms 47632 KB Output is correct
38 Correct 294 ms 57656 KB Output is correct
39 Correct 125 ms 29084 KB Output is correct
40 Correct 368 ms 48272 KB Output is correct
41 Correct 399 ms 48460 KB Output is correct
42 Correct 435 ms 57104 KB Output is correct
43 Correct 178 ms 34996 KB Output is correct
44 Correct 368 ms 39592 KB Output is correct
45 Correct 273 ms 44740 KB Output is correct
46 Correct 238 ms 45216 KB Output is correct
47 Correct 285 ms 46872 KB Output is correct
48 Correct 684 ms 76616 KB Output is correct