oj.uz

Submission #850212

# Submission time Handle Problem Language Result Execution time Memory
850212 2023-09-16T05:03:24 Z NeroZein Cities (BOI16_cities) C++17
0 / 100
 4193 ms 53704 KB 
#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, 1e15)); 
    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]]); 
    }
    cout << '\n';
  };
  for (int i = 0; i < k; ++i) {
    dij(imp[i]); 
  }
  cout << ans << '\n'; 
  return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 620 ms 27580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1420 ms 38756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4193 ms 53704 KB Output isn't correct
2 Halted 0 ms 0 KB -