제출 #490138

#제출 시각아이디문제언어결과실행 시간메모리
490138rainliofficialRobot (JOI21_ho_t4)C++17
58 / 100
3070 ms79164 KiB
#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{ 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...