//#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll K = 72;
const ll N = 1e5 + 50;
const ll inf = 1e18;
ll n, m, k, H, a[N];
ld dist[N][K];
bool mark[N];
vector<pll> adj[N];
void dfs(int v){
mark[v] = true;
for(auto [u, w]: adj[v]) if(!mark[u]) dfs(u);
}
void dijk(){
for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;
priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> pq;
for(int i = 0; i < n; i++) if(!a[i] && mark[i]){
dist[i][0] = 0; pq.push({dist[i][0], {i, 0}});
}
while (!pq.empty()){
auto [v, id] = pq.top().S;
auto vd = pq.top().F;
pq.pop();
if(vd != dist[v][id]) continue;
if(id < k){
if(dist[v][id+1] > dist[v][id]){
dist[v][id+1] = dist[v][id];
pq.push({dist[v][id+1], {v, id+1}});
}
}
if(v == H) continue;
for (auto [u, w]: adj[v]){
if(dist[u][id] > dist[v][id] + w){
dist[u][id] = dist[v][id] + w;
pq.push({dist[u][id], {u, id}});
}
if(a[u] != 2 || id == k) continue;
if(dist[u][id+1] * 2 > dist[v][id] + w){
dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
pq.push({dist[u][id+1], {u, id+1}});
}
}
}
}
void dijk2(){
for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;
priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> pq;
for(int i = 0; i < n; i++) if(i != H && mark[i]){
dist[i][0] = 0; pq.push({dist[i][0], {i, 0}});
}
while (!pq.empty()){
auto [v, id] = pq.top().S;
auto vd = pq.top().F;
pq.pop();
if(vd != dist[v][id]) continue;
if(v == H) continue;
for (auto [u, w]: adj[v]){
if(dist[u][id] > dist[v][id] + w){
dist[u][id] = dist[v][id] + w;
pq.push({dist[u][id], {u, id}});
}
if(a[u] != 2 || id == k) continue;
if(dist[u][id+1] * 2 > dist[v][id] + w){
dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
pq.push({dist[u][id+1], {u, id+1}});
}
}
}
}
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){
n = N; m = M; k = K; H = H_;
for(int i = 0; i < n; i++){
adj[i].clear(); mark[i] = false;
}
for(int i = 0; i < m; i++){
int u = x[i];
int v = y[i];
int w = c[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
for(int i = 0; i < n; i++) a[i] = arr[i];
dfs(0);
if(!mark[H]) return -1;
k = min(k, 70ll);
a[0] = 0; dijk();
ld res = dist[H][k];
/*
if(K > k){
k++; dijk2();
res = min(res, dist[H][k]);
}
*/
if(res >= inf) return -1;
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
35 ms |
4872 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
5232 KB |
Correct. |
2 |
Correct |
240 ms |
5076 KB |
Correct. |
3 |
Correct |
213 ms |
5212 KB |
Correct. |
4 |
Correct |
225 ms |
5408 KB |
Correct. |
5 |
Correct |
220 ms |
5080 KB |
Correct. |
6 |
Correct |
202 ms |
11348 KB |
Correct. |
7 |
Correct |
268 ms |
11180 KB |
Correct. |
8 |
Correct |
112 ms |
18900 KB |
Correct. |
9 |
Correct |
176 ms |
4696 KB |
Correct. |
10 |
Correct |
173 ms |
4804 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
280 ms |
5688 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
853 ms |
61888 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
101 ms |
5204 KB |
Correct. |
2 |
Correct |
111 ms |
5224 KB |
Correct. |
3 |
Correct |
117 ms |
5188 KB |
Correct. |
4 |
Correct |
133 ms |
11864 KB |
Correct. |
5 |
Correct |
85 ms |
4948 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
167 ms |
5660 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
231 ms |
5760 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
720 ms |
6984 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |