Submission #490137

# Submission time Handle Problem Language Result Execution time Memory
490137 2021-11-25T20:55:40 Z rainliofficial Robot (JOI21_ho_t4) C++17
34 / 100
719 ms 88620 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;
int n, m;
map<int, vector<Edge>> arr[MAXN];
map<int, ll> recolor[MAXN];
ll dp[MAXN];
int edge_color[MAXN], edge_cost[MAXN];
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{
			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 14388 KB Output is correct
2 Correct 7 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 12 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 10 ms 15004 KB Output is correct
10 Correct 10 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 8 ms 14796 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 10 ms 14668 KB Output is correct
17 Correct 9 ms 14796 KB Output is correct
18 Correct 8 ms 14612 KB Output is correct
19 Correct 9 ms 14668 KB Output is correct
20 Correct 9 ms 14668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 221 ms 33524 KB Output is correct
2 Correct 73 ms 24192 KB Output is correct
3 Correct 194 ms 30840 KB Output is correct
4 Correct 118 ms 27132 KB Output is correct
5 Incorrect 719 ms 88620 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14388 KB Output is correct
2 Correct 7 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 12 ms 14540 KB Output is correct
8 Correct 9 ms 14412 KB Output is correct
9 Correct 10 ms 15004 KB Output is correct
10 Correct 10 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 8 ms 14796 KB Output is correct
15 Correct 8 ms 14668 KB Output is correct
16 Correct 10 ms 14668 KB Output is correct
17 Correct 9 ms 14796 KB Output is correct
18 Correct 8 ms 14612 KB Output is correct
19 Correct 9 ms 14668 KB Output is correct
20 Correct 9 ms 14668 KB Output is correct
21 Correct 221 ms 33524 KB Output is correct
22 Correct 73 ms 24192 KB Output is correct
23 Correct 194 ms 30840 KB Output is correct
24 Correct 118 ms 27132 KB Output is correct
25 Incorrect 719 ms 88620 KB Output isn't correct
26 Halted 0 ms 0 KB -