| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1253829 | anfi | 사이버랜드 (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double INF = 1e30;
double solve(int N, int M, int K, int H,
vector<int>& x,
vector<int>& y,
vector<int>& c,
vector<int>& arr) {
K = min(K, 100);
// bangun graf
vector<vector<pair<int,int>>> adj(N);
for(int i = 0; i < M; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
// dp[u][d] = min cost reach u setelah pakai diskon d kali
vector dp(N, vector<double>(K+1, INF));
// PQ state: (dist, node u, used_discount_count)
using T = tuple<double,int,int>;
priority_queue<T, vector<T>, greater<T>> pq;
// start di (0,0) dengan cost=0
dp[0][0] = 0;
pq.push({0.0, 0, 0});
while(!pq.empty()) {
auto [dist, u, used] = pq.top(); pq.pop();
if (dist > dp[u][used]) continue;
// 1) Teleport: kalau u bertipe-0, reset cost jadi 0 di state yang sama
if (arr[u] == 0 && dist > 0) {
dp[u][used] = 0;
dist = 0;
pq.push({0, u, used});
continue; // ulangi eksplorasi dari cost=0
}
// 2) Cash-in di H kalau arr[H]==2
if (u == H && arr[H] == 2 && used < K) {
double c2 = dist/2.0;
if (c2 < dp[H][used+1]) {
dp[H][used+1] = c2;
pq.push({c2, H, used+1});
}
}
// 3) Relaksasi neighbor
for (auto [v, w] : adj[u]) {
// a) tanpa diskon
double d1 = dist + w;
if (d1 < dp[v][used]) {
dp[v][used] = d1;
pq.push({d1, v, used});
}
// b) pakai diskon di u
if (arr[u] == 2 && used < K) {
double d2 = dist + w/2.0;
if (d2 < dp[v][used+1]) {
dp[v][used+1] = d2;
pq.push({d2, v, used+1});
}
}
}
}
// ambil jawaban minimal di H
double ans = INF;
for (int d = 0; d <= K; d++)
ans = min(ans, dp[H][d]);
return (ans >= INF/2 ? -1.0 : ans);
}