Submission #490134

#	Time	Username	Problem	Language	Result	Execution time	Memory
490134		rainliofficial	Robot (JOI21_ho_t4)	C++17	58 / 100	3084 ms	93336 KiB

Main

#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 = 2e5+5, MAXM = 4e5+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] = 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();
		// 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 == 1e18) ans = -1;
	cout << ans << "\n";
}

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