| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228101 | Dzadzo | 사이버랜드 (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
// Use priority_queue instead of set for Dijkstra's algorithm
// State: (node, number of half-cost moves used)
double solve(int n, int m, int K, int h,
const vector<int>& x, const vector<int>& y,
const vector<int>& c, const vector<int>& arr) {
vector<vector<pair<int,int>>> adj(n);
for (int i = 0; i < m; i++) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
// Check reachability of h from 0
vector<bool> visited(n, false);
function<void(int)> dfs = [&](int v) {
if (visited[v]) return;
visited[v] = true;
for (auto& [to, w] : adj[v]) {
dfs(to);
}
};
dfs(0);
if (!visited[h]) return -1;
const double INF = 1e15;
int maxK = min(K, 30);
vector<vector<double>> dist(n, vector<double>(maxK + 1, INF));
// Initialize distances: start at 0 with 0 half-cost moves
priority_queue<
pair<double, pair<int,int>>,
vector<pair<double, pair<int,int>>>,
greater<>> pq;
dist[0][0] = 0;
pq.push({0.0, {0, 0}});
// Also, if arr[i]==0 and reachable, they can be considered as extra start points with zero cost
for (int i = 1; i < n; i++) {
if (!arr[i] && visited[i]) {
dist[i][0] = 0;
pq.push({0.0, {i, 0}});
}
}
while (!pq.empty()) {
auto [d, state] = pq.top();
pq.pop();
int v = state.first;
int used = state.second;
if (d > dist[v][used]) continue;
if (v == h) continue;
for (auto& [to, w] : adj[v]) {
// Regular edge
if (dist[to][used] > d + w) {
dist[to][used] = d + w;
pq.push({dist[to][used], {to, used}});
}
// Half-cost edge if allowed and special node
if (arr[to] == 2 && used < maxK) {
double nd = (d + w) / 2.0;
if (dist[to][used + 1] > nd) {
dist[to][used + 1] = nd;
pq.push({nd, {to, used + 1}});
}
}
}
}
double ans = INF;
for (int i = 0; i <= maxK; i++) {
ans = min(ans, dist[h][i]);
}
return (ans >= INF ? -1 : ans);
}