# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47242 | 2018-04-29T15:24:43 Z | PowerOfNinjaGo | Cities (BOI16_cities) | C++17 | 552 ms | 53756 KB |
//Power Of Ninja Go #include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii; #define X first #define Y second #define pb push_back const int maxn = 1e5+5; vii adj[maxn]; ll dp[32][maxn]; int main() { int n, k, m; scanf("%d %d %d", &n, &k, &m); vi imp; imp.resize(k); for(int i = 0; i< k; i++) scanf("%d", &imp[i]); for(int i = 0; i< m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); } for(int a = 0; a< 32; a++) { for(int u = 1; u<= n; u++) dp[a][u] = 1e18; } for(int i = 0; i< k; i++) { dp[1<<i][imp[i]] = 0; } for(int bit = 0; bit< (1<<k); bit++) { for(int part = 0; part<= bit; part++) { if((part | bit) != bit) continue; int rem = bit-part; for(int u = 1; u<= n; u++) dp[bit][u] = min(dp[bit][u], dp[part][u]+dp[rem][u]); } priority_queue< ii > pq; for(int i = 1; i<= n; i++) { if(dp[bit][i] != 1e18) { pq.push(ii(-dp[bit][i], i)); } } while(!pq.empty()) { ll w = -pq.top().X; int u = pq.top().Y; pq.pop(); if(dp[bit][u] != w) continue; for(auto edge : adj[u]) { int v = edge.X, w = edge.Y; if(dp[bit][v]> dp[bit][u]+w) { dp[bit][v] = dp[bit][u]+w; pq.push(ii(-dp[bit][v], v)); } } } } ll res = 2e18; for(int i = 1; i<= n; i++) res = min(res, dp[(1<<k)-1][i]); cout << res << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2936 KB | Output is correct |
2 | Correct | 4 ms | 3016 KB | Output is correct |
3 | Correct | 4 ms | 3016 KB | Output is correct |
4 | Correct | 4 ms | 3016 KB | Output is correct |
5 | Correct | 4 ms | 3092 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 203 ms | 38476 KB | Output is correct |
2 | Correct | 552 ms | 45652 KB | Output is correct |
3 | Incorrect | 100 ms | 45652 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 45652 KB | Output is correct |
2 | Correct | 10 ms | 45652 KB | Output is correct |
3 | Incorrect | 6 ms | 45652 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 218 ms | 49492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 263 ms | 53756 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |