oj.uz

Submission #202406

# Submission time Handle Problem Language Result Execution time Memory
202406 2020-02-16T03:54:51 Z quocnguyen1012 Cities (BOI16_cities) C++14
100 / 100
 3145 ms 70304 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;
const ll llinf = 1e18;

int N, K, M;
vector<int> imp;
int U[maxn], V[maxn], W[maxn];
ll f[1 << 5][maxn];
vector<int> adj[maxn];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> K >> M;
  imp.assign(K, 0);
  for (auto & x : imp){
    cin >> x;
  }
  for (int i = 1; i <= M; ++i){
    cin >> U[i] >> V[i] >> W[i];
    adj[U[i]].pb(i); adj[V[i]].pb(i);
  }
  fill_n(&f[0][0], (1 << 5) * maxn, llinf);
  for (int i = 0; i < K; ++i){
    f[1 << i][imp[i]] = 0;
  }
  for (int mask = 1; mask < (1 << K); ++mask){
    for (int a = mask; a; a = (a - 1) & mask){
      for (int i = 1; i <= N; ++i){
        f[mask][i] = min(f[mask][i], f[mask ^ a][i] + f[a][i]);
      }
    }
    for (int i = 1; i <= N; ++i){
      if (f[mask][i] != llinf){
        pq.push(mp(f[mask][i], i));
      }
    }
    while (pq.size()){
      auto now = pq.top(); pq.pop();
      if (f[mask][now.se] != now.fi) continue;
      for (int i : adj[now.se]){
        int v = U[i] + V[i] - now.se;
        if (f[mask][v] > now.fi + W[i]){
          f[mask][v] = now.fi + W[i];
          pq.push(mp(f[mask][v], v));
        }
      }
    }
  }
  ll res = llinf;
  for (int i = 1; i <= N; ++i){
    res = min(res, f[(1 << K) - 1][i]);
  }
  cout << res << '\n';
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cities.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55160 KB Output is correct
2 Correct 34 ms 55160 KB Output is correct
3 Correct 33 ms 55160 KB Output is correct
4 Correct 36 ms 55160 KB Output is correct
5 Correct 35 ms 55160 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 70304 KB Output is correct
2 Correct 696 ms 69864 KB Output is correct
3 Correct 420 ms 63752 KB Output is correct
4 Correct 125 ms 63352 KB Output is correct
5 Correct 391 ms 70116 KB Output is correct
6 Correct 106 ms 63352 KB Output is correct
7 Correct 37 ms 55288 KB Output is correct
8 Correct 35 ms 55336 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 55416 KB Output is correct
2 Correct 39 ms 55288 KB Output is correct
3 Correct 37 ms 55288 KB Output is correct
4 Correct 36 ms 55288 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 70244 KB Output is correct
2 Correct 1400 ms 69868 KB Output is correct
3 Correct 911 ms 63852 KB Output is correct
4 Correct 768 ms 67304 KB Output is correct
5 Correct 240 ms 64372 KB Output is correct
6 Correct 132 ms 64120 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2905 ms 70296 KB Output is correct
2 Correct 3145 ms 70288 KB Output is correct
3 Correct 3050 ms 69844 KB Output is correct
4 Correct 2096 ms 63852 KB Output is correct
5 Correct 1644 ms 67300 KB Output is correct
6 Correct 384 ms 64504 KB Output is correct
7 Correct 179 ms 64248 KB Output is correct