# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
749466 | 2023-05-28T05:13:46 Z | 반딧불(#9967) | Voting Cities (NOI22_votingcity) | C++17 | 269 ms | 10632 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct dat{ int x, d; ll y; dat(){} dat(int x, int d, ll y): x(x), d(d), y(y){} bool operator<(const dat &r)const{ return y>r.y; } }; int n, m, k, q; int voting[5002]; vector<pair<int, ll> > link[5002]; /// ������ ������ ll dist[5002][32]; /// dist[i][j]: i������ j�� Ƽ�� ���� �����ϴ� ��� bool visited[5002][32]; int main(){ scanf("%d %d %d", &n, &m, &k); for(int i=1; i<=k; i++) scanf("%d", &voting[i]); for(int i=1; i<=m; i++){ int x, y; ll w; scanf("%d %d %lld", &x, &y, &w); link[y].push_back(make_pair(x, w)); } priority_queue<dat> pq; for(int i=0; i<n; i++) for(int j=0; j<32; j++) dist[i][j] = 1e18; for(int i=1; i<=k; i++){ pq.push(dat(voting[i], 0, 0)); dist[voting[i]][0] = 0; } while(!pq.empty()){ dat tmp = pq.top(); pq.pop(); if(visited[tmp.x][tmp.d]) continue; int x = tmp.x, d = tmp.d; ll y = tmp.y; visited[x][d] = 1; dist[x][d] = y; // printf("%d %d: %lld\n", x, d, y); for(auto [nxt, add]: link[x]){ for(int mode=0; mode<6; mode++){ if((d >> mode) & 1) continue; int nxtD = d + (mode == 5 ? 0 : (1<<mode)); ll nxtY = y + add / 10 * (mode == 5 ? 10 : (9-mode)); pq.push(dat(nxt, nxtD, nxtY)); } } } scanf("%d", &q); while(q--){ int S; ll price[5]; scanf("%d %lld %lld %lld %lld %lld", &S, &price[0], &price[1], &price[2], &price[3], &price[4]); ll ans = 1e18; for(int d=0; d<32; d++){ if(dist[S][d] > 1e17) continue; bool able = 1; for(int i=0; i<5; i++) if(((d>>i)&1) && price[i] == -1) able = 0; if(!able) continue; ll option = dist[S][d]; for(int i=0; i<5; i++) if((d>>i)&1) option += price[i]; ans = min(ans, option); } if(ans > 1e17) puts("-1"); else printf("%lld\n", ans); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 147 ms | 6596 KB | Output is correct |
7 | Correct | 33 ms | 2004 KB | Output is correct |
8 | Correct | 164 ms | 6456 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 147 ms | 6596 KB | Output is correct |
7 | Correct | 33 ms | 2004 KB | Output is correct |
8 | Correct | 164 ms | 6456 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 214 ms | 10568 KB | Output is correct |
12 | Correct | 40 ms | 2076 KB | Output is correct |
13 | Correct | 162 ms | 6512 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 5 ms | 2100 KB | Output is correct |
7 | Correct | 36 ms | 1960 KB | Output is correct |
8 | Correct | 166 ms | 6488 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 147 ms | 6596 KB | Output is correct |
7 | Correct | 33 ms | 2004 KB | Output is correct |
8 | Correct | 164 ms | 6456 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 5 ms | 2100 KB | Output is correct |
12 | Correct | 36 ms | 1960 KB | Output is correct |
13 | Correct | 166 ms | 6488 KB | Output is correct |
14 | Correct | 154 ms | 6508 KB | Output is correct |
15 | Correct | 33 ms | 2068 KB | Output is correct |
16 | Correct | 164 ms | 6496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 161 ms | 6400 KB | Output is correct |
2 | Correct | 198 ms | 10552 KB | Output is correct |
3 | Correct | 59 ms | 2716 KB | Output is correct |
4 | Correct | 165 ms | 6484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 2632 KB | Output is correct |
2 | Correct | 18 ms | 2632 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 16 ms | 2600 KB | Output is correct |
5 | Correct | 16 ms | 2632 KB | Output is correct |
6 | Correct | 2 ms | 428 KB | Output is correct |
7 | Correct | 17 ms | 2612 KB | Output is correct |
8 | Correct | 18 ms | 2600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 4332 KB | Output is correct |
2 | Correct | 33 ms | 2004 KB | Output is correct |
3 | Correct | 164 ms | 6420 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 147 ms | 6596 KB | Output is correct |
7 | Correct | 33 ms | 2004 KB | Output is correct |
8 | Correct | 164 ms | 6456 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 214 ms | 10568 KB | Output is correct |
12 | Correct | 40 ms | 2076 KB | Output is correct |
13 | Correct | 162 ms | 6512 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 5 ms | 2100 KB | Output is correct |
17 | Correct | 36 ms | 1960 KB | Output is correct |
18 | Correct | 166 ms | 6488 KB | Output is correct |
19 | Correct | 154 ms | 6508 KB | Output is correct |
20 | Correct | 33 ms | 2068 KB | Output is correct |
21 | Correct | 164 ms | 6496 KB | Output is correct |
22 | Correct | 161 ms | 6400 KB | Output is correct |
23 | Correct | 198 ms | 10552 KB | Output is correct |
24 | Correct | 59 ms | 2716 KB | Output is correct |
25 | Correct | 165 ms | 6484 KB | Output is correct |
26 | Correct | 18 ms | 2632 KB | Output is correct |
27 | Correct | 18 ms | 2632 KB | Output is correct |
28 | Correct | 1 ms | 468 KB | Output is correct |
29 | Correct | 16 ms | 2600 KB | Output is correct |
30 | Correct | 16 ms | 2632 KB | Output is correct |
31 | Correct | 2 ms | 428 KB | Output is correct |
32 | Correct | 17 ms | 2612 KB | Output is correct |
33 | Correct | 18 ms | 2600 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 428 KB | Output is correct |
36 | Correct | 1 ms | 432 KB | Output is correct |
37 | Correct | 194 ms | 10560 KB | Output is correct |
38 | Correct | 231 ms | 10552 KB | Output is correct |
39 | Correct | 156 ms | 6424 KB | Output is correct |
40 | Correct | 1 ms | 1620 KB | Output is correct |
41 | Correct | 2 ms | 2004 KB | Output is correct |
42 | Correct | 218 ms | 10632 KB | Output is correct |
43 | Correct | 269 ms | 10576 KB | Output is correct |
44 | Correct | 161 ms | 6520 KB | Output is correct |
45 | Correct | 54 ms | 2388 KB | Output is correct |