제출 #959190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959190		kilkuwu	사이버랜드 (APIO23_cyberland)	C++17	44 / 100	32 ms	9836 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;

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

    dbg(d, u);
     
    if (u == H) continue;

    if (d > dp[u]) continue;

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

  dbg(dp);

  ans = dp[H];
  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: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3