#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e5 + 5;
int n, m, k;
vector<pair<int, int>> g[maxn];
int is_spec[maxn];
int spec[maxn];
const int MASK = (1 << 5) + 5;
struct info {
long long dist;
int mask;
int u;
bool operator<(const info &o) const {
return dist < o.dist;
}
bool operator>(const info &o) const {
return dist > o.dist;
}
};
long long d[maxn][MASK];
void solve() {
cin >> n >> k >> m;
for(int i = 1; i <= k; ++i) {
cin >> spec[i];
is_spec[spec[i]] = i;
}
for(int i = 1; i <= m; ++i) {
int u, v, w; cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
priority_queue<info, vector<info>, greater<info>> pq;
memset(d, 0x3f, sizeof(d));
for(int i = 1; i <= n; ++i) {
d[i][0] = 0;
}
for(int i = 1; i <= n; ++i) {
int mask = (is_spec[i] ? (1 << (is_spec[i] - 1)) : 0);
pq.push({0, mask, i});
d[i][mask] = 0;
}
while(!pq.empty()) {
long long dist = pq.top().dist;
int mask = pq.top().mask;
int u = pq.top().u;
pq.pop();
if(dist > d[u][mask]) continue;
// debug(u, mask, dist);
for(auto e:g[u]) {
int v = e.first, w = e.second;
for(int i = 0; i < (1 << k); ++i) {
int new_mask = i | mask;
if(is_spec[v]) {
new_mask |= (1 << (is_spec[v] - 1));
}
long long cost = dist + w + d[v][i];
if(cost < d[v][new_mask]) {
d[v][new_mask] = cost;
pq.push({cost, new_mask, v});
}
}
}
}
long long res = 1e18;
for(int i = 1; i <= n; ++i) {
res = min(res, d[i][(1 << k) - 1]);
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |