| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 900596 | Trisanu_Das | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10, MAX_K = 100;
typedef long double ld;
ld dist[2][MAX_N][MAX_K];
vector<pair<int, int> > adj[MAX_N];
ld pw[MAX_K];
double solve(int N, int M, int K, int H, std::vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for(int i = 0; i < N; i ++) g[i].resize(0);
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]});
}
K = min(K, MAX_K - 1);
for(int i = 0; i < N; i ++) for(int j = 0; j <= K; j ++) dist[0][i][j] = dist[1][i][j] = 1e18;
for(int left = K; left >= 0; left --) {
priority_queue<pair<ld, int> > pq;
for(int i = 0; i < N; i ++) {
if(i == 0) {
dist[0][i][left] = 0;
pq.push({0, i});
}
if(dist[1][i][left] < 1e17) pq.push({-dist[1][i][left], i + MAX_N});
}
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
bool used = curr.second / MAX_N;
curr.second %= MAX_N;
if(curr.second == H) continue;
if(curr.first > dist[used][curr.second][left]) continue;
for(const auto &it : adj[curr.second]) {
ld new_cost = curr.first + it.second;
if(dist[0][it.first][left] > new_cost) {
dist[0][it.first][left] = new_cost;
pq.push({-new_cost, it.first});
}
}
}
for(int i = 0; i < N; i ++) {
if(left == 0) continue;
if(arr[i] == 2) dist[1][i][left - 1] = dist[0][i][left] / 2.0;
else if(arr[i] == 0 && dist[0][i][left] < 1e17) dist[1][i][left - 1] = 0;
}
}
ld ret = min(dist[0][H][0], dist[1][H][0]);
if(ret > 1e17) return -1;
return ret;
}