Submission #1282851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282851		behrad	Cities (BOI16_cities)	C++17	100 / 100	2867 ms	142696 KiB

cities

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e5+5, mod = 1e9 + 7, inf = 2e15, SQ = 450, LG = 20;
typedef pair<ll, ll> pii;

#pragma GCC optimize("O3")
#pragma GCC target("sse4.2,tune=native")

int n, m, k, spc[7];
ll W[7][maxn], dis[maxn][32];
vector<pii> g[maxn];

inline void djk(int s, ll* dis) {
  for (int i = 1 ; i <= n ; i ++) dis[i] = inf;
  dis[s] = 0;
  priority_queue<pii, vector<pii>, greater<pii>> q;
  q.push({0, s});
  while (q.size()) {
    auto [d, v] = q.top(); q.pop();
    if (d > dis[v]) continue;
    for (auto [u, w] : g[v]) {
      if (dis[u] > dis[v] + w) {
        dis[u] = dis[v] + w;
        q.push({dis[u], u});
      }
    }
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> k >> m;
  for (int i = 0 ; i < k ; i ++) cin >> spc[i];
  for (int i = 1 , u , v , w ; i <= m ; i ++) {
    cin >> u >> v >> w;
    g[u].pb({v, w});
    g[v].pb({u, w});
  }
  
  #pragma GCC ivdep
  for (int i = 0 ; i < k ; i ++) {
    djk(spc[i], W[i]);
  }

  priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> q; // {dis, v, msk}
  for (int i = 1 ; i <= n ; i ++) {
    fill(dis[i], dis[i] + 32, inf);
    dis[i][0] = 0;
    q.push({0, i, 0});
  }

  while (q.size()) {
    auto [d, v, msk] = q.top(); q.pop();
    if (d > dis[v][msk]) continue;
    #pragma GCC ivdep
    for (auto [u, w] : g[v]) {
      if (dis[u][msk] > dis[v][msk] + w) {
        dis[u][msk] = dis[v][msk] + w;
        q.push({dis[u][msk], u, msk});
      }
    }
    #pragma GCC ivdep
    for (int i = 0 ; i < k ; i ++) {
      if (~msk >> i & 1) {
        int msk2 = msk | (1 << i);
        if (dis[v][msk2] > dis[v][msk] + W[i][v]) {
          dis[v][msk2] = dis[v][msk] + W[i][v];
          q.push({dis[v][msk2], v, msk2});
        }
      }
    }
  }

  ll ans = inf;
  for (int i = 1 ; i <= n ; i ++) ans = min(ans, dis[i][(1 << k) - 1]);
  cout << ans << nl;
}

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