Submission #640990

#	Time	Username	Problem	Language	Result	Execution time	Memory
640990		christinelynn	Cities (BOI16_cities)	C++17	36 / 100	278 ms	23684 KiB

cities

#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, dis[1003][1003], x, y, z;
long long ls[3][4] = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3}};
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++) {
      for (j=1; j<=n; j++) {
        dp[j][i] = 1e17;
      }
      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++) {
        //cout << "i: " << i << "\n";
        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";
        //cout << "\n";
        ans = min(ans, cst);
      }
    }
    cout << ans << "\n";
    otsumiko
  }
  if (n<=1000 && m<=2000 && k == 4) {
    ans = 1e17;
    for (i=1; i<=n; i++) {
      for (j=1; j<=n; j++) {
        dis[j][i] = 1e17;
      }
      dis[i][i] = 0;
      pq.push(make_pair(0, i));
      for (; !pq.empty(); ) {
        w = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if (w>dis[cn][i]) {
          continue;
        }
        for (j=0; j<al[cn].size(); j++) {
          nn = al[cn][j].first;
          ww = al[cn][j].second;
          if (dis[nn][i]>dis[cn][i]+ww) {
            dis[nn][i] = dis[cn][i]+ww;
            pq.push(make_pair(dis[nn][i], nn));
          }
        }
      }
    }
    for (i=1; i<=n; i++) {
      for (j=i; j<=n; j++) {
        for (ii=0; ii<3; ii++) {
          x = tl[ls[ii][0]];
          y = tl[ls[ii][1]];
          z = tl[ls[ii][2]];
          w = tl[ls[ii][3]];
          cst = dis[x][i]+dis[y][i]+dis[z][j]+dis[w][j]+dis[i][j];
          ans = min(ans, cst);
        }
      }
    }
    cout << ans << "\n";
    otsumiko
  }
  cout << "sek\n";
  otsumiko
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:111: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]
  111 |         for (j=0; j<al[cn].size(); j++) {
      |                   ~^~~~~~~~~~~~~~
cities.cpp:152: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]
  152 |         for (j=0; j<al[cn].size(); j++) {
      |                   ~^~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26