제출 #1097653

#제출 시각아이디문제언어결과실행 시간메모리
1097653KindaGoodGamesRobot (JOI21_ho_t4)C++14
0 / 100
3115 ms1247472 KiB
#include<bits/stdc++.h> #define ll long long #define int ll #define pii pair<int,int> #define tiii tuple<int,int,int> #define tiiii tuple<int,int,bool,int> using namespace std; int INF = numeric_limits<ll>::max()/2; int32_t main(){ int n, m; cin >> n >> m; vector<vector<tiii>> adj(n); vector<int> colorAmt(m); for(int i = 0; i < m; i++){ int a, b, c, v; cin >> a >> b >> c >> v; c--; a--;b--; adj[a].push_back({b,c,v}); adj[b].push_back({a,c,v}); colorAmt[c]++; } // Dijkstra // We use the following Idea: We can either change the current edge or all other edges. If we change all other edges, we need to keep track // of which ones we changed vector<bitset<100000>> changed(n); vector<int> dist(n, INF); // distance | vertex | color | cost | precessor priority_queue<tiiii, vector<tiiii>, greater<tiiii>> pq; pq.push({0,0,0,0}); while(pq.size()){ int d, v, c , pre; tie(d,v,c, pre) = pq.top(); pq.pop(); if(d >= dist[v]) continue; dist[v] = d; changed[v] = changed[pre]; if(c) changed[v][pre] = c; for(auto p : adj[v]){ if(get<0>(p) == pre) continue; int s = 0; // get the sum of taking all other edges for(auto e : adj[v]){ int u, co, we; tie(u,co,we) = e; // if the colors don't match or it's the edge backwards, ignore if(co != get<1>(p) || get<0>(e) == get<0>(p)) continue; s += we; } // only taking one edge if(get<2>(p) < s){ pq.push({get<2>(p)+d, get<0>(p), 0, v}); }else{ pq.push({s+d, get<0>(p), 1, v}); } } // either change the color of this edge or all others } if(dist[n-1]>=INF) dist[n-1] = -1; cout << dist[n-1] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...