# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
230384 | 2020-05-10T02:08:32 Z | arnold518 | Cities (BOI16_cities) | C++14 | 3106 ms | 51368 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const ll INF = 1e18; int N, M, K; int A[10]; vector<pii> adj[MAXN+10]; ll dist[MAXN+10][40]; struct Queue { int v; ll w; bool operator < (const Queue &p) const { return w>p.w; } }; int main() { int i, j, k; scanf("%d%d%d", &N, &K, &M); for(i=0; i<K; i++) scanf("%d", &A[i]); for(i=1; i<=M; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for(i=1; i<=N; i++) for(j=1; j<(1<<K); j++) dist[i][j]=INF; for(i=0; i<K; i++) dist[A[i]][(1<<i)]=0; for(i=1; i<(1<<K); i++) { for(k=1; k<=N; k++) { for(j=i&(i-1); j; j=i&(j-1)) { dist[k][i]=min(dist[k][j]+dist[k][i^j], dist[k][i]); } } priority_queue<Queue> PQ; for(k=1; k<=N; k++) PQ.push({k, dist[k][i]}); while(!PQ.empty()) { Queue now=PQ.top(); PQ.pop(); if(now.w>dist[now.v][i]) continue; for(auto &nxt : adj[now.v]) { if(dist[nxt.first][i]>now.w+nxt.second) { dist[nxt.first][i]=now.w+nxt.second; PQ.push({nxt.first, dist[nxt.first][i]}); } } } } ll ans=INF; for(i=1; i<=N; i++) ans=min(ans, dist[i][(1<<K)-1]); printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2688 KB | Output is correct |
2 | Correct | 6 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2688 KB | Output is correct |
4 | Correct | 6 ms | 2688 KB | Output is correct |
5 | Correct | 6 ms | 2688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 785 ms | 51020 KB | Output is correct |
2 | Correct | 782 ms | 51040 KB | Output is correct |
3 | Correct | 474 ms | 42876 KB | Output is correct |
4 | Correct | 93 ms | 11040 KB | Output is correct |
5 | Correct | 401 ms | 50936 KB | Output is correct |
6 | Correct | 92 ms | 11040 KB | Output is correct |
7 | Correct | 9 ms | 3072 KB | Output is correct |
8 | Correct | 8 ms | 3072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 3072 KB | Output is correct |
2 | Correct | 11 ms | 3072 KB | Output is correct |
3 | Correct | 9 ms | 3072 KB | Output is correct |
4 | Correct | 9 ms | 2944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1526 ms | 51176 KB | Output is correct |
2 | Correct | 1506 ms | 51148 KB | Output is correct |
3 | Correct | 1043 ms | 43280 KB | Output is correct |
4 | Correct | 837 ms | 32012 KB | Output is correct |
5 | Correct | 222 ms | 16216 KB | Output is correct |
6 | Correct | 101 ms | 12668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3069 ms | 51332 KB | Output is correct |
2 | Correct | 3014 ms | 51368 KB | Output is correct |
3 | Correct | 3106 ms | 51168 KB | Output is correct |
4 | Correct | 2117 ms | 43144 KB | Output is correct |
5 | Correct | 1601 ms | 32252 KB | Output is correct |
6 | Correct | 297 ms | 16088 KB | Output is correct |
7 | Correct | 112 ms | 12684 KB | Output is correct |