Submission #490132

# Submission time Handle Problem Language Result Execution time Memory
490132 2021-11-25T20:45:32 Z rainliofficial Robot (JOI21_ho_t4) C++17
0 / 100
3000 ms 32276 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 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[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;
	}
	// return 0;
	for (int i=0; i<n; i++){
		dp[i] = 1e18;
	}
	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();
		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 == 1e18) ans = -1;
	cout << ans << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14448 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14336 KB Output is correct
5 Correct 11 ms 14400 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 38 ms 14596 KB Output is correct
8 Correct 9 ms 14480 KB Output is correct
9 Correct 12 ms 15064 KB Output is correct
10 Correct 10 ms 14924 KB Output is correct
11 Correct 10 ms 14800 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 9 ms 14748 KB Output is correct
14 Correct 9 ms 14796 KB Output is correct
15 Execution timed out 3062 ms 14668 KB Time limit exceeded
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 32276 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14448 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14336 KB Output is correct
5 Correct 11 ms 14400 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 38 ms 14596 KB Output is correct
8 Correct 9 ms 14480 KB Output is correct
9 Correct 12 ms 15064 KB Output is correct
10 Correct 10 ms 14924 KB Output is correct
11 Correct 10 ms 14800 KB Output is correct
12 Correct 8 ms 14668 KB Output is correct
13 Correct 9 ms 14748 KB Output is correct
14 Correct 9 ms 14796 KB Output is correct
15 Execution timed out 3062 ms 14668 KB Time limit exceeded
16 Halted 0 ms 0 KB -