fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll long long
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 1000001
  13. #define INF (1ll<<30)
  14. #define NAME "file"
  15. using namespace std;
  16.  
  17. ll n, m, q, k, cnt ;
  18. ll a[MAXN] ;
  19. ll lab[MAXN] ;
  20. ll have_important[MAXN ] ;
  21. vector<ll> important ;
  22. vector<ll> adj[MAXN ] ;
  23. bool visited[MAXN ] ;
  24.  
  25. void dfs(ll u ) {
  26.     if(visited[u]) return ;
  27.     visited[u] = true ;
  28.     cnt ++ ;
  29. for(ll v : adj[u]) if(!visited[v]) dfs(v ) ;
  30. }
  31.  
  32. ll find_set(ll a ) {
  33.     return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  34. }
  35.  
  36. bool union_set(ll a, ll b ) {
  37.     a = find_set(a) ;
  38.     b = find_set(b) ;
  39.     if(a == b ) return false ;
  40.     if(have_important[a] && have_important[b]) return false ;
  41.     if(lab[a] > lab[b]) swap(a, b ) ;
  42.     lab[a] += lab[b] ;
  43.     adj[a].push_back(b) ;
  44.     adj[b].push_back(a ) ;
  45.     have_important[a] += have_important[b] ;
  46.     lab[b] = a ;
  47.     return true ;
  48. }
  49.  
  50. struct Edge {
  51.     ll u, v, w ;
  52.     bool operator < ( const Edge & other ) const {
  53.         return w < other.w ;
  54.     }
  55. };
  56.  
  57. vector < Edge > e ;
  58.  
  59. void init() {
  60.     cin >> n >> m >> k ;
  61.  
  62.     FOR(i, 1, n ) lab[i] = - 1 ;
  63.  
  64.     FOR(i, 1, k ) {
  65.         ll x  ;
  66.         cin >> x ;
  67.         important.push_back(x) ;
  68.         have_important[x] = 1 ;
  69.     }
  70.     FOR(i, 1, m ) {
  71.         ll x, y, w ;
  72.         cin >> x >> y >> w ;
  73.         e.push_back({x, y, w }) ;
  74.     }
  75.     sort(e.begin(), e.end() ) ;
  76. }
  77.  
  78. void solve() {
  79.     ll cnt = 0, ans = 0 ;
  80.     for(auto [u, v, w ] : e ) {
  81.         if(union_set(u, v )) {
  82.             ans += w ;
  83. //            cout << " ok " << el ;
  84.         }
  85.     }
  86.  
  87.     FOR(i , 1 , n ) {
  88.     if(lab[i] < 0 ) {
  89.         if(!have_important[find_set(i)]) {
  90.             cout << -1 << el ;
  91.             return ;
  92.         }
  93.     }
  94.     }
  95. //    cout << cnt << " cnt " << el ;
  96. //    if(cnt != n ) {
  97. //        cout << -1 << el ;
  98. //        return ;
  99. //    }
  100.     cout << ans << el ;
  101. }
  102.  
  103. _ROOT_ {
  104.     // freopen(NAME".inp" , "r" , stdin);
  105.     // freopen(NAME".out" , "w", stdout) ;
  106.     ios_base::sync_with_stdio(0);
  107.     cin.tie(0);
  108.     cout.tie(0);
  109.     int t = 1; // cin >> t ;
  110.     while(t--) {
  111.         init();
  112.         solve();
  113.     }
  114.     return (0&0);
  115. }
  116.  
Success #stdin #stdout 0.01s 28364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/j34FxB
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!