// ----------------------- TEMPLATE NO.4 ---------------------------
#ifndef ONLINE_JUDGE
#include "D:\File cua Wayzz\DSA\Debug Template\template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll, ll>
const ll mod = 1e9 + 7;
const int N = 1e5 + 100;
const ll oo = 1e16;
// loops
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ROF(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
// others :>
#define nl '\n'
//----------------------------------SOLUTION-----------------------------------//
int n, m, k;
ll dp[1<<5][N];
vector<ii> adj[N];
bool minimize(ll& a, ll b){
if(a > b) {a = b; return 1;}
return 0;
}
void solve(){
cin >> n >> k >> m;
vector<int> cities(k);
for(int &v : cities) cin >> v;
FOR(i, 1, m){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
FOR(mask, 1, (1 << k) - 1) FOR(i, 1, n){
dp[mask][i] = oo;
}
FOR(i, 0, k-1) dp[1<<i][cities[i]] = 0;
FOR(mask, 1, (1 << k) - 1){
for(int submask = (mask - 1) & mask; submask > 0; submask = (submask - 1) & mask){
FOR(i, 1, n) minimize(dp[mask][i], dp[submask][i] + dp[mask - submask][i]);
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
FOR(i, 1, n) if(dp[mask][i] != oo){
pq.push({i, dp[mask][i]});
}
while(!pq.empty()){
auto [u, dist] = pq.top();
pq.pop();
if(dist > dp[mask][u]) continue;
for(auto [v, w] : adj[u]){
if(minimize(dp[mask][v], dp[mask][u] + w)){
pq.push({v, dp[mask][v]});
}
}
}
}
ll res = oo;
FOR(i, 1, n) minimize(res, dp[(1<<k)-1][i]);
cout << res;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Wayzz "name"
if (fopen (Wayzz".inp", "r")) {
freopen (Wayzz".inp", "r", stdin);
freopen (Wayzz".out", "w", stdout);
}
int T = 1;
while(T--) solve();
cerr <<"\nTime Elapse: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
Compilation message
cities.cpp:3:10: fatal error: D:\File cua Wayzz\DSA\Debug Template\template.cpp: No such file or directory
3 | #include "D:\File cua Wayzz\DSA\Debug Template\template.cpp"
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
