oj.uz

답안 #641072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641072 2022-09-16T00:08:22 Z kith14 Cities (BOI16_cities) C++14
22 / 100
 308 ms 36320 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 1e5+5, MOD = 1e9+7, M = 2e5+5;
ll tc = 1, n, m, ar[N], used[25];
ll x, y, k, dis[N][5], nx[N][5];
string s, s1, s2, ye = "YES", no = "NO";
vector<lpairll> ed[N];
vector<lpairll> V;
vector<ll> pk[5];
ll xr[M], wr[M], yr[M], pr[25];

void input(){
  cin >> n >> k >>  m;
  repp(i,1,k) cin >> ar[i], used[ar[i]] = 1;
  repp(i,1,m){
    ll x, y, w;
    cin >> xr[i] >> yr[i] >> wr[i];
    x = xr[i], y = yr[i], w = wr[i];
    ed[x].pb(mp(y,mp(w,i)));
    ed[y].pb(mp(x,mp(w,i)));
    V.pb(mp(w,mp(x,y)));
  }
}

ll fir(ll i){
  if (i == pr[i]) return i;
  return pr[i] = fir(pr[i]);
}

bool merge(ll a, ll b){
  a = fir(a), b = fir(b);
  if (a == b) return 0;
  pr[a] = b;
  return 1;
}

void sub1(){
  //create an mst with the nodes that are active
  vector<ll> act;
  repp(i,1,n){
    if (!used[i]) act.pb(i);
  }
  ll sz = act.size(), ans = 1e18;
  repp(i,0,(1<<sz)){
    repz(j,0,sz){
      if((1<<j)&i) used[act[j]] = 1;
      else used[act[j]] = 0;
    }
    // cout << "i = " << i << endl;
    // repp(j,1,n){
    //   cout << j << " " << used[j] << endl;
    // }
    ll cur = 0;
    repp(j,1,n) pr[j] = j;
    for (auto j : V){
      ll w = j.fr, x = j.sc.fr, y = j.sc.sc;
      if (!used[x] || !used[y]) continue;
      if(merge(x,y)) cur += w;
    }
    // repp(j,1,n){
    //   cout << j << " " << fir(j) << endl;
    // }
    bool imp = 0;
    repp(j,1,k){
      imp |= (fir(ar[j]) != fir(ar[1]));
    }
    if (imp) continue;
    ans = min(ans,cur);
  }
  cout << ans << endl;
}

void subk2(ll st, ll fn, ll cr){
  repp(i,1,n) dis[i][cr] = 1e18,  nx[i][cr] = n+1;
  dis[ar[st]][cr] = nx[ar[st]][cr] = 0;
  priority_queue<pairll,vector<pairll>,greater<pairll> > pq;
  pq.push(mp(0,ar[st]));
  while(pq.size()){
    pairll a = pq.top();
    pq.pop();
    for (auto i : ed[a.sc]){
      ll nxidx = i.fr, w = i.sc.fr;
      if (dis[nxidx][cr] > dis[a.sc][cr]+w){
        dis[nxidx][cr] = dis[a.sc][cr]+w;
        nx[nxidx][cr] = i.sc.sc;
        pq.push(mp(dis[nxidx][cr],nxidx));
      }
    }
  }
  // cout << "cr = " << cr << endl;
  // repp(i,1,n) cout << dis[i][cr] << " ";
  // cout << endl;
  // repp(i,1,n) cout << nx[i][cr] << " ";
  // cout << endl;
  // ll cur = ar[fn];
  // while(cur != ar[st]){
  //   ll ed = nx[cur][cr];
  //   pk[cr].pb(ed);
  //   if (xr[ed] == cur){
  //     cur = yr[ed];
  //   }
  //   else cur = xr[ed];
  // }
  // for (auto i : pk[cr]) cout << i << " ";
  // cout << endl;
}

void subk3(){
  subk2(1,2,1);
  subk2(2,3,2);
  subk2(3,1,3);

  ll ans = 1e18;
  repp(xex,1,3){
    ll cur = 0;
    repp(pep,1,3){
      cur += dis[ar[pep]][xex];
    }
    ans = min(ans,cur);
  }
  cout << ans << endl;
}

void solve(){
  if (n <= 20 && m <= 40){
    sort(V.begin(),V.end());
    sub1();
  }
  else if (k == 2){
    subk2(1,2,1);
    cout << dis[ar[2]][1] << endl;
  }
  else if (k == 3){
    subk3();
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 75 ms 2696 KB Output is correct
3 Correct 42 ms 2692 KB Output is correct
4 Correct 24 ms 2712 KB Output is correct
5 Correct 13 ms 2644 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 308 ms 36320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 26572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 116 ms 26604 KB Output isn't correct
2 Halted 0 ms 0 KB -