# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
848323 | 2023-09-12T06:20:28 Z | KN200711 | Voting Cities (NOI22_votingcity) | C++14 | 422 ms | 15200 KB |
# include <bits/stdc++.h> # define ll long long # define fi first # define se second using namespace std; int N, E, K; vector<int> T; vector< pair<int, ll> > edge[5001]; ll dp[32][5001]; bool vis[32][5001]; int main() { scanf("%d %d %d", &N, &E, &K); T.resize(K); for(int i=0;i<K;i++) { scanf("%d", &T[i]); } for(int i=0;i<E;i++) { int a, b; ll c; scanf("%d %d %lld", &a, &b, &c); edge[a].push_back(make_pair(b, c)); edge[b].push_back(make_pair(a, c)); } for(int i=0;i<32;i++) { for(int k=0;k<N;k++) dp[i][k] = -1; } priority_queue< pair<int, pair<ll, int> > > PQ; for(int i=0;i<K;i++) { PQ.push(make_pair(0, make_pair(0, T[i]))); } while(!PQ.empty()) { int a, c; ll b; a = -PQ.top().fi; b = -PQ.top().se.fi; c = PQ.top().se.se; PQ.pop(); if(dp[a][c] != -1) continue; dp[a][c] = b; for(auto p : edge[c]) { for(int k=0;k<5;k++) { if(!(a&(1 << k))) { if(dp[a^(1 << k)][c] == -1) PQ.push(make_pair(-(a ^ (1 << k)), make_pair(-b - (10 - k - 1) * p.se / 10, p.fi))); } } if(dp[a][p.fi] == -1) { PQ.push(make_pair(-a, make_pair(-b-p.se, p.fi))); } } } int Q; scanf("%d", &Q); while(Q--) { int S; ll P[5]; scanf("%d", &S); for(int i=0;i<5;i++) scanf("%lld", &P[i]); ll as = 0ll, ans = 1e18; for(int i=0;i<32;i++) { // cout<<"i : "<<i<<" "<<dp[i][S]<<endl; if(dp[i][S] == -1) continue; as = dp[i][S]; for(int k=0;k<5;k++) { if(i&(1 << k)) { if(P[k] == -1) as = 1e18; else as += P[k]; } } ans = min(ans, as); } if(ans >= 1e18) ans = -1; printf("%lld\n", ans); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 422 ms | 15200 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 2260 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 375 ms | 15040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |