Submission #850213

#	Time	Username	Problem	Language	Result	Execution time	Memory
850213		NeroZein	Cities (BOI16_cities)	C++17	0 / 100	3996 ms	48812 KiB

cities

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;

using T = array<long long, 3>;

vector<pair<int, int>> g[N]; 

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k, m;
  cin >> n >> k >> m;
  vector<int> imp(k);
  for (int i = 0; i < k; ++i) {
    cin >> imp[i];
  }
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w); 
  }
  auto get_ind = [&](int x) {
    for (int i = 0; i < k; ++i) {
      if (imp[i] == x) {
        return i; 
      }
    }
    return -1; 
  };
  long long ans = LLONG_MAX;
  auto dij = [&](int src) {
    vector<vector<long long>> dis(1 << k, vector<long long> (n + 1, 1e16)); 
    dis[get_ind(src)][src] = 0; 
    priority_queue<T, vector<T>, greater<T>> pq; 
    pq.push({0, get_ind(src), src}); 
    while (!pq.empty()) {
      auto [c, s, v] = pq.top();
      pq.pop();
      if (c != dis[s][v]) {
        continue;
      }
      for (auto [u, w] : g[v]) {
        long long nc = c + w;
        int ind = get_ind(u);
        long long ns = s | (ind == -1 ? 0 : 1 << ind); 
        if (nc < dis[ns][u]) {
          dis[ns][u] = nc;
          pq.push({nc, ns, u}); 
        }
      }
    }
    for (int i = 0; i < k; ++i) {
      ans = min(ans, dis[(1 << k) - 1][imp[i]]); 
    }
  };
  for (int i = 0; i < k; ++i) {
    dij(imp[i]); 
  }
  cout << ans << '\n'; 
  return 0;
}

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