이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ld double
#define tp3 tuple<ld, int, int>
const int K = 4;
const ld D = 2, INF = LLONG_MAX;
int n, h, k;
vector<int> arr;
vector<ld> mn;
vector<vector<vector<ld>>> dis;
vector<vector<pair<int, ld>>> adj;
void dijkstra(int x, int idx) {
priority_queue<tp3> pq;
if (idx == 1) {
for (int i = 0; i < n; i++) {
if (arr[i] || dis[0][0][i] == INF) continue;
pq.push(make_tuple(-0, 0, i));
}
}
else {
pq.push(make_tuple(-0, 0, x));
}
while (!pq.empty()) {
ld d = -get<0>(pq.top());
int divs = get<1>(pq.top());
int y = get<2>(pq.top());
pq.pop();
if (dis[idx][divs][y] <= d) continue;
dis[idx][divs][y] = d;
if (y == h) continue;
if (mn[y] != INF && arr[y] == 2 && divs+1 < min(k+1, K) && dis[idx][divs+1][y] > ((d+mn[y]) / D)) {
pq.push(make_tuple(-((d+mn[y]) / D), divs+1, y));
}
for (auto& [z, d2] : adj[y]) {
if (dis[idx][divs][z] > (d+d2)) {
pq.push(make_tuple(-(d+d2), divs, z));
}
if (arr[z] == 2 && divs+1 < min(k+1, K) && dis[idx][divs+1][z] > ((d+d2) / D)) {
pq.push(make_tuple(-((d+d2) / D), divs+1, z));
}
}
}
}
double solve(int N, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) {
n = N;
h = H;
k = K;
arr.clear();
arr = ARR;
adj.clear();
adj.resize(n);
for (int i = 0; i < m; i++) {
adj[x[i]].push_back(make_pair(y[i], c[i]));
adj[y[i]].push_back(make_pair(x[i], c[i]));
}
mn.clear();
mn.resize(n);
for (int i = 0; i < n; i++) {
mn[i] = INF;
for (auto& [j, d] : adj[i]) {
if (j == h) continue;
mn[i] = min(mn[i], d);
}
}
dis.clear();
dis.resize(2, vector<vector<ld>>(K, vector<ld>(n)));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < K; j++) {
for (int k = 0; k < n; k++) {
dis[i][j][k] = INF;
}
}
}
dijkstra(0, 0);
dijkstra(0, 1);
ld ans = INF;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < min(K, k+1); j++) {
ans = min(ans, dis[i][j][h]);
}
}
return (ans == INF ? (ld)(-1) : ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |