Submission #959186

#	Time	Username	Problem	Language	Result	Execution time	Memory
959186		kilkuwu	Cyberland (APIO23_cyberland)	C++17	0 / 100	26 ms	7252 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

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

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;

  while (pq.size()) {
    auto [d, u] = pq.top();
    pq.pop();

    if (d > dp[u]) continue;

    for (auto [v, w] : adj[u]) {
      auto nd = dp[v] + w;
      if (nd < dp[v]) {
        dp[v] = nd;
        pq.emplace(nd, v);
      }
    }
  }

  ans = dp[H];
  return (ans < 1e18 ? ans : -1);
}

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