Submission #202406

#	Time	Username	Problem	Language	Result	Execution time	Memory
202406		quocnguyen1012	Cities (BOI16_cities)	C++14	100 / 100	3145 ms	70304 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26