제출 #1097658

#제출 시각아이디문제언어결과실행 시간메모리
1097658KindaGoodGamesRobot (JOI21_ho_t4)C++14
0 / 100
406 ms33932 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,-1}); 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; map<int,int> occ; int old = 0; for(auto e : adj[v]){ int u, co, we; tie(u,co,we) = e; // if the color was if(u == pre )old = we; if(u == pre && c) continue; memo[co] += we; occ[co]++; } for(auto p : adj[v]){ //if(get<0>(p) == pre) continue; int s = memo[get<1>(p)]; // only taking one edge // int rem = 0; // if(c) rem = old; if(get<2>(p) < s-get<2>(p)){ pq.push({get<2>(p)+d, get<0>(p), 1, v}); } else if(occ[get<1>(p)] > 1){ pq.push({s+d-get<2>(p), get<0>(p), 0, v}); } else if(occ[get<1>(p)] == 1) { pq.push({d, get<0>(p), 0, 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; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int32_t main()':
Main.cpp:47:13: warning: variable 'old' set but not used [-Wunused-but-set-variable]
   47 |         int old = 0;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...