# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
147317 |
2019-08-28T19:57:57 Z |
cerberus |
Cities (BOI16_cities) |
C++17 |
|
3383 ms |
168952 KB |
/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1e5 + 10, K = 5, S = (1 << K) + 10;
const ll inf = 1e15 + 42;
struct state_t {
int mask, u;
ll val;
bool operator<(const state_t &o) const {
return val > o.val;
}
};
int imp[K];
vector<pii> g[N];
vector<int> supermasks[S];
ll dp[S][N];
int main() {
fast_cin();
int n, k, m;
cin >> n >> k >> m;
for (int i = 0; i < k; ++i) {
cin >> imp[i];
}
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].pb({v, w});
g[v].pb({u, w});
}
int tot = (1 << k), all = tot - 1;
for (int mask = 1; mask < tot; ++mask) {
for (int u = 1; u <= n; ++u) {
dp[mask][u] = inf;
}
}
for (int mask = 0; mask < tot; ++mask) {
if (__builtin_popcount(mask) > 1) {
continue;
}
for (int smask = mask; smask < tot; ++smask) {
if ((smask & mask) == mask) {
supermasks[mask].pb(smask);
}
}
}
priority_queue<state_t> q;
for (int i = 0; i < k; ++i) {
dp[1 << i][imp[i]] = 0;
q.push({1 << i, imp[i], 0});
}
while (!q.empty()) {
auto cur = q.top();
q.pop();
int mask = cur.mask, u = cur.u;
if (dp[mask][u] != cur.val) {
continue;
}
for (auto &nmask : supermasks[mask]) {
int extra = nmask ^ mask;
for (auto &e : g[u]) {
int v = e.first, w = e.second;
ll cand = dp[mask][u] + w + dp[extra][v];
if (cand < dp[nmask][v]) {
dp[nmask][v] = cand;
q.push({nmask, v, cand});
}
}
}
}
ll ans = inf;
for (int u = 1; u <= n; ++u) {
ans = min(ans, dp[all][u]);
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
579 ms |
35360 KB |
Output is correct |
2 |
Correct |
569 ms |
34944 KB |
Output is correct |
3 |
Correct |
313 ms |
17640 KB |
Output is correct |
4 |
Correct |
100 ms |
11772 KB |
Output is correct |
5 |
Correct |
343 ms |
19788 KB |
Output is correct |
6 |
Correct |
88 ms |
11264 KB |
Output is correct |
7 |
Correct |
7 ms |
3192 KB |
Output is correct |
8 |
Correct |
7 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
3700 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1310 ms |
57840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3383 ms |
168952 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |