fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 1111
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<60)
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q, k, type ;
  21. ll a[MAXN] ;
  22. ll d[MAXN / 10 ][1 << 10 ] ;
  23. ll lab[MAXN ] ;
  24. vector<pair<ll,ll>> adj[MAXN ] ;
  25. vector<ll> spec ;
  26.  
  27.  
  28. struct Edge {
  29.     ll u, v, w ;
  30.     bool operator < (const Edge & other ) const {
  31.         return w < other.w ;
  32.     }
  33. } edge[MAXN ] ;
  34.  
  35. ll find_set(ll a ) {
  36.     return lab[a] < 0 ? a : lab[a] = find_set(lab[a]) ;
  37. }
  38.  
  39. struct Data {
  40.     ll u, mask, w ;
  41.     bool operator < (const Data & other )const {
  42.         return w > other.w ;
  43.     }
  44. };
  45.  
  46. bool union_set(ll a, ll b ) {
  47.     a = find_set(a) ;
  48.     b = find_set(b) ;
  49.     if(a == b ) return false ;
  50.     if(lab[a] > lab[b]) swap(a, b ) ;
  51.     lab[a] += lab[b] ;
  52.     lab[b] = a ;
  53.     return true ;
  54. }
  55.  
  56. void init() {
  57.     cin >> n >> k >> m >> type  ;
  58.     FOR(i, 1, k ) {
  59.         ll x ;
  60.         cin >> x ;
  61.         spec.push_back(x) ;
  62.     }
  63.     FOR(i, 1, m ) {
  64.         ll x, y, w ;
  65.         cin >> x >> y >> w ;
  66.         edge[i] = {x, y, w } ;
  67.         adj[x].push_back({y, w }) ;
  68.         adj[y].push_back({x, w }) ;
  69.     }
  70. }
  71.  
  72. void solve() {
  73.     sort(edge + 1, edge + m + 1 ) ;
  74.     memset(lab, -1, sizeof lab ) ;
  75.     ll ans = INF ;
  76.     if(k == n && type == 1 ) {
  77.         ll mst = 0 ;
  78.         FOR(i, 1, m ) {
  79.             if(union_set(edge[i].u, edge[i].v )) mst += edge[i].w ;
  80.         }
  81.         cout << mst << el ;
  82.         return ;
  83.     }
  84.     if(type == 1 ) {
  85.         FOR(i, 0, n ) REP(mask, 1 << k ) d[i][mask] = INF ;
  86.         REP(i, k ) d[spec[i]][1 << i ] = 0 ;
  87.         REP(mask, 1 << k ) {
  88.             if(mask == 0 ) continue ;
  89.  
  90.             FOR(i, 1, n  ) {
  91.                 for(ll sub_mask = mask ; sub_mask ; sub_mask = mask & (sub_mask - 1 )) d[i][mask] = min(d[i][mask], d[i][sub_mask] + d[i][sub_mask ^ mask ]) ;
  92.             }
  93.  
  94.             priority_queue<Data > pq ;
  95.             FOR(i, 1, n ) if(d[i][mask] != INF ) pq.push({i, mask, d[i][mask] }) ;
  96.             while(!pq.empty() ) {
  97.                 Data u = pq.top() ;
  98.                 pq.pop() ;
  99.                 if(d[u.u][u.mask ] < u.w ) continue ;
  100.                 for(pair<ll,ll> v : adj[u.u] ) if(d[v.fi][u.mask] > u.w + v.se ) pq.push({v.fi, u.mask, d[v.fi][u.mask] = u.w + v.se }) ;
  101.             }
  102.         }
  103.         FOR(i, 1, n ) ans = min(ans, d[i][(1 << k ) - 1 ]) ;
  104.         cout << ans << el ;
  105.     } else {
  106.         vector<ll> in_mst(n + 10, 1 ) ;
  107.         ll cnt_active = n ;
  108.         for(ll v : spec ) in_mst[v] = false, cnt_active --  ;
  109.         REP(mask, 1 << k ) {
  110.             REP(i, k ) if(mask >> i & 1 ) in_mst[spec[i]] = true, cnt_active ++  ;
  111.             FOR(i, 1, n ) lab[i] = -1 ;
  112.             ll cc = 0, mst = 0 ;
  113.             FOR(i, 1, m ) if(in_mst[edge[i].u] && in_mst[edge[i].v] && union_set(edge[i].u, edge[i].v ) ) {
  114.                 cc ++ ;
  115.                 mst += edge[i].w ;
  116.             }
  117.             if(cnt_active - 1 == cc ) ans = min(ans, mst ) ;
  118.  
  119.             REP(i, k ) if(mask >> i & 1 ) in_mst[spec[i]] = false, cnt_active -- ;
  120.         }
  121.         cout << ans << el ;
  122.     }
  123. }
  124.  
  125.  
  126. _ROOT_ {
  127. //    freopen(NAME".inp", "r", stdin);
  128. //    freopen(NAME".out", "w", stdout) ;
  129.     ios_base::sync_with_stdio(0);
  130.     cin.tie(0);
  131.     cout.tie(0);
  132.     int t = 1; // cin >> t ;
  133.     while(t--) {
  134.         init();
  135.         solve();
  136.     }
  137.     return (0&0);
  138. }
  139.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1152921504606846976
https://ideone.com/JbNXGt
language:
C++14 (gcc 8.3)
created:
5 days 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!