# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
879446 | 2023-11-27T12:59:15 Z | KN200711 | Cities (BOI16_cities) | C++14 | 297 ms | 23696 KB |
# include <bits/stdc++.h> # define ll long long # define fi first # define se second using namespace std; vector< pair<int, ll> > edge[100001]; ll dist[100001], mn[100001]; bool vis[100001]; int main() { int N, K, M; scanf("%d %d %d", &N, &K, &M); vector<int> ipr(K); for(int i=0;i<K;i++) { scanf("%d", &ipr[i]); } for(int i=0;i<M;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<K;i++) { priority_queue< pair<ll, int> > PQ; PQ.push(make_pair(0ll, ipr[i])); for(int c=1;c<=N;c++) vis[c] = 0; while(!PQ.empty()) { ll a = PQ.top().fi; int b = PQ.top().se; PQ.pop(); if(vis[b]) continue; vis[b] = 1; dist[b] -= a; for(int c=0;c<edge[b].size();c++) { if(!vis[edge[b][c].fi]) PQ.push(make_pair(a - 1ll * edge[b][c].se, edge[b][c].fi)); } } } ll ans = 1e18; for(int d=1;d<=N;d++) { ans = min(ans, dist[d]); } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4188 KB | Output is correct |
2 | Correct | 1 ms | 4188 KB | Output is correct |
3 | Correct | 2 ms | 4188 KB | Output is correct |
4 | Incorrect | 1 ms | 4188 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 209 ms | 22452 KB | Output is correct |
2 | Correct | 208 ms | 22028 KB | Output is correct |
3 | Correct | 55 ms | 11600 KB | Output is correct |
4 | Correct | 146 ms | 23696 KB | Output is correct |
5 | Correct | 170 ms | 22208 KB | Output is correct |
6 | Correct | 110 ms | 23592 KB | Output is correct |
7 | Correct | 2 ms | 4440 KB | Output is correct |
8 | Correct | 2 ms | 4284 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 4444 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 297 ms | 22276 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 272 ms | 22412 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |