제출 #1097657

#제출 시각아이디문제언어결과실행 시간메모리
1097657KindaGoodGamesRobot (JOI21_ho_t4)C++14
0 / 100
283 ms30524 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<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; // get all costs map<int,int> memo; 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 // || get<0>(e) == get<0>(p) memo[get<1>(e)] += we; } for(auto p : adj[v]){ if(get<0>(p) == pre) continue; int s = memo[get<1>(p)]; // only taking one edge if(get<2>(p) < s-get<2>(p)){ pq.push({get<2>(p)+d, get<0>(p), 0, v}); }else{ pq.push({s+d-get<2>(p), get<0>(p), 1, v}); } } // either change the color of this edge or all others } if(dist[n-1]>=INF/2) 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...