Submission #959191

#	Time	Username	Problem	Language	Result	Execution time	Memory
959191		kilkuwu	Cyberland (APIO23_cyberland)	C++17	68 / 100	294 ms	13120 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

template <typename T>
using PQG = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
  std::vector<std::vector<std::pair<int, int>>> adj(N);
  for (int i = 0; i < M; i++) {
    int u = x[i], v = y[i], w = c[i];
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  PQG<std::pair<double, int>> pq;
  double ans = 1e18;

  std::vector<double> dp(N, 1e18);
  pq.emplace(0, 0);
  dp[0] = 0;

  K = std::min(K, 100);

  while (K--) {
    std::vector<double> ndp(N, 1e18);
    PQG<std::pair<double, int>> npq;
    while (pq.size()) {
      auto [d, u] = pq.top();
      pq.pop();

      if (u == H) continue;

      if (d > dp[u]) continue;

      for (auto [v, w] : adj[u]) {
        if (arr[v] <= 1) {
          auto nd = (d + w) * arr[v];
          if (nd < dp[v]) {
            dp[v] = nd;
            pq.emplace(nd, v);
          }
        } else {
          auto nd = d + w;
          if (nd < dp[v]) {
            dp[v] = nd;
            pq.emplace(nd, v);
          }
          nd /= 2;
          if (nd < ndp[v]) {
            ndp[v] = nd;
            npq.emplace(nd, v);
          }
        }
      }
    }

    ans = std::min(ans, dp[H]);
    std::swap(pq, npq);
    std::swap(dp, ndp);
  }

  return (ans < 1e18 ? ans : -1);
}

#ifdef LOCAL
#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3