#include<bits/stdc++.h>
/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 2e5 + 7 , mod = 1e9 + 7 ;
const int inf = N ;
// How interesting!
int n , k , m;
bool imp[N] ;
int fat[N] ;
vector<pair<int,pii>> ed;
vector<pii> adj[N] ;
int st[N], en[N] , t;
int up[N][20] ;
ll pref[N] ;
ll ans ;
inline int find(int x){fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
inline bool upper(int u ,int v){return st[u] <= st[v] && en[v] <= en[u] ; }
inline bool cmp(int u , int v){return st[u] <= st[v] ; }
void link(int u , int v, int c){
int u0 = u , v0 = v ;
u = find(u) ;
v = find(v) ;
if(u != v){
fat[u] = v ;
adj[u0].push_back({v0 , c}) ;
adj[v0].push_back({u0 , c}) ;
}
}
void dfs(int x , int p){
st[x] = ++ t;
up[x][0] = p ;
for(int i = 1 ;i < 20 ; ++ i)
up[x][i] = up[up[x][i-1]][i-1] ;
for(auto u : adj[x]){
if(u.first == p)
continue ;
pref[u.first] = pref[x] + u.second ;
dfs(u.first, x) ;
}
en[x] = ++ t;
}
int lca(int u , int v){
if(upper(u , v))return u ;
if(upper(v , u))return v ;
for(int i = 19 ; ~i ; -- i){
if(!upper(up[u][i] , v)){
u = up[u][i] ;
}
}
return up[u][0] ;
}
void build(vector<int> &vec){
int sz = (int) vec.size() ;
sort(vec.begin() , vec.end() , cmp) ;
for(int i = 1; i < sz ;++ i){
vec.push_back(lca(vec[i-1],vec[i])) ;
}
sort(vec.begin() , vec.end() , cmp) ;
vector<int> aux = {vec[0]} ;
for(int i = 1; i < (int) vec.size() ; ++ i){
int j = vec[i] ;
while(aux.size() > 1 && !upper(aux.back() , j) ){
int u = aux[aux.size() - 2];
int v = aux.back();
ans += pref[v] - pref[u] ;
aux.pop_back() ;
}
aux.push_back(j) ;
}
while(aux.size() > 1){
int u = aux[aux.size() - 2];
int v = aux.back();
ans += pref[v] - pref[u] ;
aux.pop_back() ;
}
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n >> k >> m ;
vector<int> vec ;
for(int i = 0 ;i < N ; ++ i)
fat[i] = i ;
for(int i = 0 ;i < k ; ++ i){
int x; cin >> x;
vec.push_back(x) ;
imp[x] = 1;
}
for(int i = 0 ;i < m; ++ i){
int u , v , c;
cin >> u >> v >> c ;
ed.push_back({c,{u , v}}) ;
}
sort(ed.begin(), ed.end()) ;
for(auto u : ed){
link(u.second.first , u.second.second, u.first) ;
}
dfs(1 , 1) ;
build(vec) ;
cout<< ans;
return 0 ;
}
Compilation message
cities.cpp: In function 'int find(int)':
cities.cpp:35:68: warning: no return statement in function returning non-void [-Wreturn-type]
35 | inline int find(int x){fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
190 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
176 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
275 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
266 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
