oj.uz

답안 #959192

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959192 2024-04-07T15:55:39 Z kilkuwu 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1303 ms 10816 KB 
#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);

  for (int kk = 0; kk <= K; kk++) {
    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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 600 KB Correct.
2 Correct 20 ms 540 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 600 KB Correct.
2 Correct 26 ms 816 KB Correct.
3 Correct 22 ms 604 KB Correct.
4 Correct 23 ms 604 KB Correct.
5 Correct 25 ms 600 KB Correct.
6 Correct 21 ms 1440 KB Correct.
7 Correct 31 ms 1440 KB Correct.
8 Correct 10 ms 2648 KB Correct.
9 Correct 21 ms 348 KB Correct.
10 Correct 24 ms 784 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 348 KB Correct.
2 Correct 30 ms 344 KB Correct.
3 Correct 25 ms 604 KB Correct.
4 Correct 24 ms 348 KB Correct.
5 Correct 23 ms 344 KB Correct.
6 Correct 5 ms 1116 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 6704 KB Correct.
2 Correct 100 ms 592 KB Correct.
3 Correct 82 ms 596 KB Correct.
4 Correct 91 ms 596 KB Correct.
5 Correct 49 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 604 KB Correct.
2 Correct 22 ms 348 KB Correct.
3 Correct 21 ms 604 KB Correct.
4 Correct 19 ms 1308 KB Correct.
5 Correct 19 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 604 KB Correct.
2 Correct 20 ms 608 KB Correct.
3 Correct 32 ms 8500 KB Correct.
4 Correct 13 ms 1208 KB Correct.
5 Correct 22 ms 540 KB Correct.
6 Correct 21 ms 604 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 600 KB Correct.
2 Correct 17 ms 604 KB Correct.
3 Correct 345 ms 10816 KB Correct.
4 Correct 241 ms 4868 KB Correct.
5 Correct 371 ms 9900 KB Correct.
6 Correct 188 ms 7072 KB Correct.
7 Correct 244 ms 4048 KB Correct.
8 Correct 205 ms 2792 KB Correct.
9 Correct 89 ms 1496 KB Correct.
10 Correct 90 ms 1452 KB Correct.
11 Correct 175 ms 2388 KB Correct.
12 Correct 114 ms 1464 KB Correct.
13 Correct 101 ms 1620 KB Correct.
14 Correct 226 ms 7140 KB Correct.
15 Correct 227 ms 3904 KB Correct.
16 Correct 97 ms 1580 KB Correct.
17 Correct 116 ms 1620 KB Correct.
18 Correct 121 ms 1480 KB Correct.
19 Correct 313 ms 2332 KB Correct.
20 Correct 5 ms 472 KB Correct.
21 Correct 8 ms 604 KB Correct.
22 Correct 14 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 788 KB Correct.
2 Correct 47 ms 604 KB Correct.
3 Correct 146 ms 10576 KB Correct.
4 Correct 315 ms 1116 KB Correct.
5 Correct 1169 ms 9576 KB Correct.
6 Correct 503 ms 7072 KB Correct.
7 Correct 579 ms 6764 KB Correct.
8 Correct 252 ms 2844 KB Correct.
9 Correct 208 ms 1432 KB Correct.
10 Correct 206 ms 1364 KB Correct.
11 Correct 148 ms 2016 KB Correct.
12 Correct 251 ms 1444 KB Correct.
13 Correct 229 ms 1540 KB Correct.
14 Correct 1303 ms 7736 KB Correct.
15 Correct 1031 ms 7812 KB Correct.
16 Correct 420 ms 4444 KB Correct.
17 Correct 293 ms 2744 KB Correct.
18 Correct 222 ms 1628 KB Correct.
19 Correct 287 ms 1616 KB Correct.
20 Correct 257 ms 1556 KB Correct.
21 Correct 867 ms 2588 KB Correct.
22 Correct 10 ms 344 KB Correct.
23 Correct 18 ms 604 KB Correct.
24 Correct 38 ms 1116 KB Correct.