제출 #942176

#제출 시각아이디문제언어결과실행 시간메모리
942176vjudge1Voting Cities (NOI22_votingcity)C++17
15 / 100
57 ms4068 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int N, E, K; cin >> N >> E >> K; vector<int> T(K); for(auto &i : T) cin >> i; vector<vector<pair<int, int>>> adj(N); for(int i = 0; i < E; i++){ int u, v, c; cin >> u >> v >> c; adj[v].push_back({u, c}); } vector<vector<long long>> dist(32, vector<long long>(N, 1e18)); vector<vector<bool>> vis(32, vector<bool>(N, false)); priority_queue<tuple<long long, int, int>> q; for(int i = 0; i < K; i++){ dist[0][T[i]] = 0; q.push({0, 0, T[i]}); } while(!q.empty()){ int mask = get<1>(q.top()); int x = get<2>(q.top()); q.pop(); if(vis[mask][x]) continue; vis[mask][x] = true; for(pair<int, int> p : adj[x]){ int node = p.first; int c = p.second; if(dist[mask][node] > dist[mask][x] + c){ dist[mask][node] = dist[mask][x] + c; q.push({-dist[mask][node], mask, node}); } for(int b = 0; b < 5; b++){ if(!((1 << b) & mask)){ int nmask = mask + (1 << b); long long w = (c * (9 - b)) / 10; if(dist[nmask][node] > dist[mask][x] + w){ dist[nmask][node] = dist[mask][x] + w; q.push({-dist[nmask][node], nmask, node}); } } } } } int Q; cin >> Q; while(Q--){ int S; cin >> S; vector<int> P(5); for(auto &i : P) cin >> i; long long ans = 1e18; for(int i = 0; i < 32; i++){ long long cost = dist[i][S]; for(int b = 0; b < 5; b++){ if((1 << b) & i){ if(P[b] == -1) cost = 1e18; else cost += P[b]; } } ans = min(ans, cost); } if(ans == 1e18) cout << -1 << "\n"; else cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...