| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1314231 | aaaaaaaa | 사이버랜드 (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
const double inf = 1e18;
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) {
vector<pair<int, double>> adj[N + 1];
for(int i = 0; i < M; ++i){
adj[x[i]].push_back({y[i], (double) c[i] * 1.00});
adj[y[i]].push_back({x[i], (double) c[i]} * 1.00);
}
vector<vector<double>> dp(N + 1, vector<double>(K + 1, inf));
priority_queue<tuple<int, int, int>> pq;
pq.push({0, -K, 0}); dp[0][K] = 0;
while(pq.size()){
auto [dist, rem, node] = pq.top();
pq.pop(); dist = -dist, rem = -rem;
if(node == H) continue;
if(arr[node] == 0) dist = 0;
if(dp[node][rem] < dist) continue;
for(auto [v, w] : adj[node]){
if(dp[v][rem] > dist + w){
dp[v][rem] = dist + w;
pq.push({-dp[v][rem], -rem, v});
}
if(arr[node] == 2 && rem && dist > 0.0){
if(dp[v][rem - 1] > (dist / 2.0) + w){
dp[v][rem - 1] = (dist / 2.0) + w;
pq.push({-dp[v][rem - 1], -(rem - 1), v});
}
}
}
}
double ans = inf;
for(int i = 0; i <= K; ++i) ans = min(ans, dp[H][i]);
return ((ans >= inf || ans <= 0) ? -1 : ans);
}