제출 #64425

#제출 시각아이디문제언어결과실행 시간메모리
64425zetapiCities (BOI16_cities)C++14
0 / 100
73 ms17036 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define int long long #define itr ::iterator typedef pair<int,int> pii; const int MAX=1e5; pair<int,pii> edge[MAX]; vector<pii> vec[MAX]; int N,K,M,res,arr[MAX],mark[MAX],height[MAX],Parent[MAX]; int par[MAX],ranks[MAX]; void init() { for(int A=1;A<=N;A++) { par[A]=A; ranks[A]=0; } return ; } int root(int X) { if(par[X]==X) return X; return par[X]=root(par[X]); } void unions(int X,int Y) { int u=root(X),v=root(Y); if(ranks[u]>ranks[v]) swap(u,v); par[u]=v; ranks[u]+=(ranks[u]==ranks[v]); return ; } void dfs(int node,int par,int h) { height[node]=h; for(auto A:vec[node]) { if(A.first==par) continue; Parent[A.first]=node; dfs(A.first,node,h+1); } return ; } void dfs(int node,int par) { for(auto A:vec[node]) { if(A.first==par) continue; if(mark[A.first]) res+=A.second; dfs(A.first,node); } return ; } signed main() { ios_base::sync_with_stdio(false); cin>>N>>K>>M; for(int A=1;A<=K;A++) cin>>arr[A]; for(int A=1;A<=M;A++) cin>>edge[A].second.first>>edge[A].second.second>>edge[A].first; sort(edge+1,edge+M+1); init(); for(int A=1;A<=M;A++) { if(root(edge[A].second.first)!=root(edge[A].second.second)) { unions(edge[A].second.first,edge[A].second.second); vec[edge[A].second.first].pb(mp(edge[A].second.second,edge[A].first)); vec[edge[A].second.second].pb(mp(edge[A].second.first,edge[A].first)); } } dfs(1,0,0); int u,v; for(int A=1;A<=K;A++) { for(int B=A+1;B<=K;B++) { u=arr[A]; v=arr[B]; if(height[u]>height[v]) swap(u,v); while(height[v]>height[u]) { mark[v]=1; v=Parent[v]; } while(u!=v) { u=Parent[u]; v=Parent[v]; mark[u]=1; mark[v]=1; } } } dfs(1,0); cout<<res; 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...