#include <bits/stdc++.h>
using namespace std;
#ifdef KURUMI
#include "algo/debug.h"
#endif
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
if(seed == 0) return rand(l, r);
else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}
template<typename T> bool maximize(T &a, T b) {
if(a < b) {
a = b;
return true;
}else return false;
}
template<typename T> bool minimize(T &a, T b) {
if(a > b) {
a = b;
return true;
}else return false;
}
typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;
const int N = 2e5 + 3;
int n, k, m;
vector<int> imp;
vector<pii> adj[N];
void input() {
cin >> n >> k >> m;
imp.resize(k);
for(int i = 0; i < k; i++) {
cin >> imp[i];
}
for(int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
}
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dp[N][1 << 5 | 3];
void process() {
memset(dp, 0x3f, sizeof(dp));
for(int mask = 1; mask < (1 << k); mask++) {
if(__builtin_popcount(mask) == 1) {
int i = 31 - __builtin_clz(mask);
dp[imp[i]][1 << i] = 0;
}
for(int submask = mask; submask > 0; submask = (submask - 1) & mask) {
for(int i = 1; i <= n; i++) {
minimize(dp[i][mask], dp[i][submask] + dp[i][mask ^ submask]);
}
}
priority_queue<pli, vector<pli>, greater<pli>> pq;
for(int i = 1; i <= n; i++) if(dp[i][mask] != INF) {
pq.emplace(dp[i][mask], i);
}
while(!pq.empty()) {
ll cost; int u; tie(cost, u) = pq.top(); pq.pop();
if(cost > dp[u][mask]) continue;
for(auto [v, w] : adj[u]) {
if(minimize(dp[v][mask], dp[u][mask] + w)) {
pq.emplace(dp[v][mask], v);
}
}
}
}
ll answer = INF;
for(int i = 1; i <= n; i++) {
minimize(answer, dp[i][(1 << k) - 1]);
}
cout << answer << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "Deeto"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int testcase = 1; // cin >> testcase;
for(int i = 1; i <= testcase; i++) {
input();
process();
}
cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
return 0;
}
Compilation message (stderr)
cities.cpp: In function 'int main()':
cities.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |