Submission #1082580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082580		Wjsc	Cities (BOI16_cities)	C++14	100 / 100	5782 ms	89260 KiB

cities

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pi pair<int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int N = 1e5 + 5,
          INF = 1e17;

int n, k, m;
int b[N];
int f[N][70];
vector<pi> ad[N];

void Dij(int st) { // st - mask
  using tp = tuple<int, int, int>;
  priority_queue<tp, vector<tp>, greater<tp>> q;

  for(int i = 1; i <= n; ++i) q.emplace(f[i][st], i, st);

  while(q.size()) {
    int c, u, mask; tie(c, u, mask) = q.top();
    q.pop();

    if(f[u][mask] < c) continue;

    for(auto x : ad[u]) {
      int v, w; tie(v, w) = x;
      int nMask = mask | b[v];
      if(f[v][nMask] > c + w) f[v][nMask] = c + w, q.emplace(f[v][nMask], v, nMask);
    }
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  if(fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  cin >> n >> k >> m;
  for(int i = 1, id = 0; i <= k; ++i) {
    int x; cin >> x;
    b[x] = (1 << id++);
  }

  for(int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    ad[u].emplace_back(v, w);
    ad[v].emplace_back(u, w);
  }

  memset(f, 21, sizeof f);

  for(int i = 1; i <= n; ++i) f[i][b[i]] = 0;

  for(int mask = 0; mask < (1 << k); ++mask) {
    for(int sub1 = 0; sub1 < (1 << k); ++sub1) {
      int sub2 = mask ^ sub1;
      for(int i = 1; i <= n; ++i) f[i][mask] = min(f[i][mask], f[i][sub1] + f[i][sub2]);
    }
    Dij(mask);
  }

  int ans = INF;
  for(int i = 1; i <= n; ++i) ans = min(ans, f[i][(1 << k) - 1]);
  cout << ans;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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