#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
const ll N = 1e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], used[25];
ll x, y, k, dis[N][5], nx[N][5];
string s, s1, s2, ye = "YES", no = "NO";
vector<lpairll> ed[N];
vector<lpairll> V;
vector<ll> pk[5];
ll xr[N], wr[N], yr[N], pr[25];
void input(){
cin >> n >> k >> m;
repp(i,1,k) cin >> ar[i], used[ar[i]] = 1;
repp(i,1,m){
ll x, y, w;
cin >> xr[i] >> yr[i] >> wr[i];
x = xr[i], y = yr[i], w = wr[i];
ed[x].pb(mp(y,mp(w,i)));
ed[y].pb(mp(x,mp(w,i)));
V.pb(mp(w,mp(x,y)));
}
}
ll fir(ll i){
if (i == pr[i]) return i;
return pr[i] = fir(pr[i]);
}
bool merge(ll a, ll b){
a = fir(a), b = fir(b);
if (a == b) return 0;
pr[a] = b;
return 1;
}
void sub1(){
//create an mst with the nodes that are active
vector<ll> act;
repp(i,1,n){
if (!used[i]) act.pb(i);
}
ll sz = act.size(), ans = 1e18;
repp(i,0,(1<<sz)){
repz(j,0,sz){
if((1<<j)&i) used[act[j]] = 1;
else used[act[j]] = 0;
}
// cout << "i = " << i << endl;
// repp(j,1,n){
// cout << j << " " << used[j] << endl;
// }
ll cur = 0;
repp(j,1,n) pr[j] = j;
for (auto j : V){
ll w = j.fr, x = j.sc.fr, y = j.sc.sc;
if (!used[x] || !used[y]) continue;
if(merge(x,y)) cur += w;
}
// repp(j,1,n){
// cout << j << " " << fir(j) << endl;
// }
bool imp = 0;
repp(j,1,k){
imp |= (fir(ar[j]) != fir(ar[1]));
}
if (imp) continue;
ans = min(ans,cur);
}
cout << ans << endl;
}
void subk2(ll st, ll fn, ll cr){
repp(i,1,n) dis[i][cr] = 1e18, nx[i][cr] = n+1;
dis[ar[st]][cr] = nx[ar[st]][cr] = 0;
priority_queue<pairll,vector<pairll>,greater<pairll> > pq;
pq.push(mp(0,ar[st]));
while(pq.size()){
pairll a = pq.top();
pq.pop();
for (auto i : ed[a.sc]){
ll nxidx = i.fr, w = i.sc.fr;
if (dis[nxidx][cr] > dis[a.sc][cr]+w){
dis[nxidx][cr] = dis[a.sc][cr]+w;
nx[nxidx][cr] = i.sc.sc;
pq.push(mp(dis[nxidx][cr],nxidx));
}
}
}
// cout << "cr = " << cr << endl;
// repp(i,1,n) cout << dis[i][cr] << " ";
// cout << endl;
// repp(i,1,n) cout << nx[i][cr] << " ";
// cout << endl;
ll cur = ar[fn];
while(cur != ar[st]){
ll ed = nx[cur][cr];
pk[cr].pb(ed);
if (xr[ed] == cur){
cur = yr[ed];
}
else cur = xr[ed];
}
// for (auto i : pk[cr]) cout << i << " ";
// cout << endl;
}
void subk3(){
subk2(1,2,1);
subk2(2,3,2);
subk2(3,1,3);
ll ans = 1e18;
repp(xex,1,3){
set<ll> setz;
repp(i,1,3){
if (i != xex){
for (auto j : pk[i]) setz.insert(j);
}
}
ll tot = 0;
for (auto i : setz){
tot += wr[i];
}
ans = min(ans,tot);
}
cout << ans << endl;
}
void solve(){
if (n <= 20 && m <= 40){
sort(V.begin(),V.end());
sub1();
}
else if (k == 2){
subk2(1,2,1);
cout << dis[ar[2]][1] << endl;
}
else if (k == 3){
subk3();
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//cin >> tc;
while(tc--){
input();
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
81 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
44 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
25 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
16 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
28556 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
28476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
28520 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
