#include <iostream>
#include <climits>
#include <queue>
using namespace std;
typedef long long int Z;
int n, k, m;
vector<int> imp;
vector<vector<pair<int, Z>>> G;
Z d[32][202020];
Z huge = LLONG_MAX / 3;
bool seen[202020];
int main() {
cin >> n >> k >> m;
imp.resize(k);
for(int i = 0; i < k; ++i) {
cin >> imp[i];
--imp[i];
}
G.resize(n);
for(int i = 0; i < m; ++i) {
int a, b;
Z c;
cin >> a >> b >> c;
--a;
--b;
G[a].emplace_back(b, c);
G[b].emplace_back(a, c);
}
fill((Z*)d, (Z*)d + 32 * 202020, huge);
for(int i = 0; i < k; ++i) {
d[1 << i][imp[i]] = 0;
}
priority_queue<pair<Z, int>> Q;
for(int c = 1; c < (1 << k); ++c) {
for(int a = 0; a < c; ++a) {
if((a | c) != c) continue;
int b = c ^ a;
if(b > a) continue;
for(int v = 0; v < n; ++v) {
d[c][v] = min(d[c][v], d[a][v] + d[b][v]);
}
}
fill(seen, seen + n, false);
for(int v = 0; v < n; ++v) {
if(d[c][v] == huge) continue;
Q.emplace(-d[c][v], v);
}
while(!Q.empty()) {
Z cost = -Q.top().first;
int v = Q.top().second;
Q.pop();
if(seen[v]) continue;
seen[v] = true;
for(auto edge : G[v]) {
Z ec = cost + edge.second;
if(ec < d[c][edge.first]) {
d[c][edge.first] = ec;
Q.emplace(-ec, edge.first);
}
}
}
}
Z res = huge;
for(int v = 0; v < n; ++v) {
res = min(res, d[(1 << k) - 1][v]);
}
cout << res << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
52724 KB |
Output is correct |
2 |
Correct |
3 ms |
52724 KB |
Output is correct |
3 |
Correct |
6 ms |
52724 KB |
Output is correct |
4 |
Correct |
9 ms |
52724 KB |
Output is correct |
5 |
Correct |
6 ms |
52724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
943 ms |
71636 KB |
Output is correct |
2 |
Correct |
946 ms |
71516 KB |
Output is correct |
3 |
Correct |
553 ms |
63424 KB |
Output is correct |
4 |
Correct |
246 ms |
61704 KB |
Output is correct |
5 |
Correct |
603 ms |
71616 KB |
Output is correct |
6 |
Correct |
256 ms |
61696 KB |
Output is correct |
7 |
Correct |
3 ms |
53000 KB |
Output is correct |
8 |
Correct |
9 ms |
53000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
53000 KB |
Output is correct |
2 |
Correct |
16 ms |
52988 KB |
Output is correct |
3 |
Correct |
23 ms |
52856 KB |
Output is correct |
4 |
Correct |
9 ms |
52856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1673 ms |
71636 KB |
Output is correct |
2 |
Correct |
1649 ms |
71252 KB |
Output is correct |
3 |
Correct |
1169 ms |
63424 KB |
Output is correct |
4 |
Correct |
1016 ms |
67404 KB |
Output is correct |
5 |
Correct |
433 ms |
64068 KB |
Output is correct |
6 |
Correct |
249 ms |
64936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3066 ms |
71624 KB |
Output is correct |
2 |
Correct |
3133 ms |
71608 KB |
Output is correct |
3 |
Correct |
2973 ms |
71332 KB |
Output is correct |
4 |
Correct |
2063 ms |
63428 KB |
Output is correct |
5 |
Correct |
1579 ms |
67396 KB |
Output is correct |
6 |
Correct |
579 ms |
64072 KB |
Output is correct |
7 |
Correct |
276 ms |
65180 KB |
Output is correct |