oj.uz

답안 #640978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640978 2022-09-15T15:53:33 Z andecaandeci Cities (BOI16_cities) C++17
22 / 100
 152 ms 20104 KB 
#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, k, m, u, v, c, tl[6], tp[100069], pw[22], pr[100069], ci, ctu, ans = 1e17, cst, dp[100069][4], w, ww, cn, nn;
pair<long long, pair<long long, long long> > ed[100069];
vector<pair<long long, long long> > al[100069];
mikodanye pq;
set<long long> st;

long long fd(long long x) {
  if (pr[x] != x) {
    pr[x] = fd(pr[x]);
  }
  return pr[x];
}

int main() {
  nyahalo
  long long i, j, ii;
  pw[0] = 1;
  for (i=1; i<=21; i++) {
    pw[i] = pw[i-1]*2;
  }
  cin >> n >> k >> m;
  for (i=1; i<=n; i++) {
    tp[i] = 0;
    pr[i] = i;
    dp[i][1] = 1e17;
    dp[i][2] = 1e17;
    dp[i][3] = 1e17;
  }
  for (i=1; i<=k; i++) {
    cin >> tl[i];
    tp[tl[i]] = 1;
  }
  for (i=1; i<=m; i++) {
    cin >> ed[i].second.first >> ed[i].second.second >> ed[i].first;
    u = ed[i].second.first;
    v = ed[i].second.second;
    c = ed[i].first;
    al[u].push_back(make_pair(v, c));
    al[v].push_back(make_pair(u, c));
    
  }
  sort(ed+1, ed+m+1);
  if (n<=20 && m<=40) {
    for (i=0; i<=pw[n]-1; i++) {
      ctu = 0;
      for (j=1; j<=k; j++) {
        ci = tl[j];
        if ((i&pw[ci-1]) == 0) {
          ctu = 1;
          break;
        }
      }
      if (ctu == 1) {
        continue;
      }
      for (j=1; j<=n; j++) {
        pr[j] = j;
      }
      cst = 0;
      for (j=1; j<=m; j++) {
        c = ed[j].first;
        u = ed[j].second.first;
        v = ed[j].second.second;
        if ((i&pw[u-1]) == 0 || (i&pw[v-1]) == 0) {
          continue;
        }
        if (fd(u) != fd(v)) {
          cst += c;
          pr[fd(u)] = fd(v);
        }
      }
      for (j=1; j<=n; j++) {
        if ((i&pw[j-1]) == 0) {
          continue;
        }
        st.insert(fd(j));
      }
      if (st.size()>1) {
        cst = 1e17;
      }
      st.clear();
      ans = min(ans, cst);
    }
    cout << ans << "\n";
    otsumiko
  }
  if (k<=3) {
    for (i=1; i<=k; i++) {
      u = tl[i];
      dp[u][i] = 0;
      pq.push(make_pair(0, u));
      for (; !pq.empty(); ) {
        w = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if (w>dp[cn][i]) {
          continue;
        }
        for (j=0; j<al[cn].size(); j++) {
          nn = al[cn][j].first;
          ww = al[cn][j].second;
          if (dp[nn][i]>dp[cn][i]+ww) {
            dp[nn][i] = dp[cn][i]+ww;
            pq.push(make_pair(dp[nn][i], nn));
          }
        }
      }
    }
    if (k == 2) {
      v = tl[2];
      ans = dp[v][1];
    } else {
      for (i=1; i<=n; i++) {
        cst = dp[i][1]+dp[i][2]+dp[i][3];
        //cout << "cst: " << cst << "\n";
        //cout << "dp1: " << dp[i][1] << " dp2: " << dp[i][2] << " dp3: " << dp[i][3] << "\n";
        ans = min(ans, cst);
      }
    }
    cout << ans << "\n";
    otsumiko
  }
  cout << "sek\n";
  otsumiko
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:107:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (j=0; j<al[cn].size(); j++) {
      |                   ~^~~~~~~~~~~~~~
cities.cpp:24:19: warning: unused variable 'ii' [-Wunused-variable]
   24 |   long long i, j, ii;
      |                   ^~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 152 ms 2684 KB Output is correct
3 Correct 80 ms 2696 KB Output is correct
4 Correct 41 ms 2644 KB Output is correct
5 Correct 25 ms 2644 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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