제출 #749808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749808		NeroZein	사이버랜드 (APIO23_cyberland)	C++17	0 / 100	673 ms	21060 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using T = pair<double, int>;

vector<int> a;
vector<bool> vis; 
vector<int> zeros;
vector<vector<pair<int, int>>> g; 
void Dfs (int v) {
  vis[v] = true;
  if (a[v] == 0) {
    zeros.push_back(v);
  }
  for (auto [u, w] : g[v]) {
    if (!vis[u]) {
      Dfs(u); 
    }
  }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
  g.resize(N);
  a.resize(N);
  vis.resize(N);
  K = min(K, 90); 
  for (int i = 0; i < M; ++i) {
    g[x[i]].emplace_back(y[i], c[i]); 
    g[y[i]].emplace_back(x[i], c[i]); 
  }
  vis[H] = true; 
  Dfs(0); 
  double ans = 1e18;
  vector<vector<double>> cost(K + 1, vector<double>(N, 1e18)); 
  cost[0][0] = 0;
  for (int i : zeros) {
    cost[0][i] = 0; 
  }
  for (int i = 0; i <= K; ++i) {
    priority_queue<T, vector<T>, greater<T>> pq; 
    for (int j = 0; j < N; ++j) {
      if (cost[i][j] != 1e18) {
        pq.push({cost[i][j], j});
      }
      while (!pq.empty()) {
        auto [c, v] = pq.top();
        pq.pop();
        if (c > cost[i][v]) {
          continue;
        }
        for (auto [u, w] : g[v]) {
          if (arr[u] == 2) {
            if (i < K && (c + w) / 2.0 < cost[i + 1][u]) {
              cost[i + 1][u] = (c + w) / 2.0; 
            }
          }
          if (c + w < cost[i][u]) {
            cost[i][u] = c + w; 
            pq.push({cost[i][u], u});
          }
        }
      }
    }
  }
  for (int i = 0; i <= K; ++i) {
    ans = min(ans, cost[i][H]); 
  }
  for (int i = 0; i < N; ++i) {
    g[i].clear(); 
    vis[i] = 0; 
  }
  zeros.clear();
  return ans == 1e18 ? -1.0 : ans; 
}

• 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