제출 #693678

#제출 시각아이디문제언어결과실행 시간메모리
693678ajab_01Cities (BOI16_cities)C++17
0 / 100
879 ms262144 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int LOG = 20; vector<pair<int , int> > g[N] , adj[N]; vector<pair<int , pair<int , int> > > edge; vector<int> vec; int jad[N][LOG] , level[N] , sz[N] , par[N] , val[N] , lc = -1 , n , k , m; bool vis[N]; long long ans; int get(int u){ if(u != par[u]) par[u] = get(par[u]); return par[u]; } void merge(int u , int v){ if(sz[u] < sz[v]) swap(u , v); sz[u] += sz[v]; par[v] = u; } void find_mst(){ for(int i = 1 ; i <= n ; i++){ sz[i] = 1; par[i] = i; } sort(edge.begin() , edge.end()); for(auto x : edge){ int u = x.second.first , v = x.second.second , w = x.first; if(get(u) != get(v)){ merge(u , v); adj[u].push_back({v , w}); adj[v].push_back({u , w}); } } } void dfs(int ver , int pr){ for(auto j : adj[ver]){ int i = j.first; if(i == pr) continue; level[i] = level[ver] + 1; jad[i][0] = ver; for(int k = 1 ; k < LOG ; k++) jad[i][k] = jad[jad[i][k - 1]][k - 1]; dfs(i , ver); } } int lca(int u , int v){ if(level[u] > level[v]) swap(u , v); int dis = level[v] - level[u]; for(int i = LOG - 1 ; i >= 0 ; i--) if(dis & (1 << i)) v = jad[v][i]; if(v == u) return v; for(int i = LOG - 1 ; i >= 0 ; i--){ if(jad[v][i] != jad[u][i]){ u = jad[u][i]; v = jad[v][i]; } } return jad[v][0]; } void cal(int ver , int pr){ for(auto j : adj[ver]){ int i = j.first , w = j.second; if(i == pr) continue; val[i] = w; par[i] = ver; cal(i , ver); } } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> k >> m; for(int i = 0 ; i < k ; i++){ int vertex; cin >> vertex; vec.push_back(vertex); } for(int i = 0 ; i < m ; i++){ int u , v , w; cin >> u >> v >> w; g[u].push_back({v , w}); g[v].push_back({u , w}); edge.push_back({w , {u , v}}); } find_mst(); dfs(1 , 0); for(int i : vec){ if(lc == -1){ lc = i; continue; } lc = lca(lc , i); } cal(1 , 0); for(int i : vec){ int vertex = i; while(vertex != lc){ vis[vertex] = 1; vertex = par[vertex]; } } for(int i = 2 ; i <= n ; i++) if(vis[i]) ans += val[i]; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...