#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const double INF = 1e18;
const double eps = 1e-10;
int N, M, K, H, A[MAXN+10];
vector<pii> adj[MAXN+10];
bool vis[MAXN+10];
double dist[MAXN+10][40], P[40];
struct Queue
{
int v, k; double w;
bool operator < (const Queue &p) const { return w>p.w; }
};
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+1;
for(int i=1; i<=N; i++) A[i]=_arr[i-1];
for(int i=0; i<M; i++)
{
int u=_x[i]+1, v=_y[i]+1, w=_c[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
K=min(K, 30);
for(int i=1; i<=N; i++) vis[i]=false;
queue<int> Q;
vis[1]=true; Q.push(1); vis[H]=true;
while(!Q.empty())
{
int now=Q.front(); Q.pop();
for(auto nxt : adj[now])
{
if(vis[nxt.first]) continue;
Q.push(nxt.first);
vis[nxt.first]=true;
}
}
for(int i=1; i<=N; i++) if(A[i]==0 && !vis[i]) A[i]=1;
for(int i=1; i<=N; i++) for(int j=0; j<=K; j++) dist[i][j]=INF;
priority_queue<Queue> PQ;
dist[H][0]=0;
PQ.push({H, 0, 0});
P[0]=1;
for(int i=1; i<=K; i++) P[i]=P[i-1]/2;
A[1]=0;
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(fabs(dist[now.v][now.k]-now.w)>eps) continue;
//printf("%d %d %.10lf\n", now.v, now.k, now.w);
if(A[now.v]==0) continue;
for(auto nxt : adj[now.v])
{
if(nxt.first!=H && now.w+P[now.k]*nxt.second<dist[nxt.first][now.k])
{
dist[nxt.first][now.k]=now.w+P[now.k]*nxt.second;
PQ.push({nxt.first, now.k, now.w+P[now.k]*nxt.second});
}
}
if(A[now.v]==2)
{
for(auto nxt : adj[now.v])
{
if(nxt.first!=H && now.w+P[now.k+1]*nxt.second<dist[nxt.first][now.k+1])
{
dist[nxt.first][now.k+1]=now.w+P[now.k+1]*nxt.second;
PQ.push({nxt.first, now.k+1, now.w+P[now.k+1]*nxt.second});
}
}
}
}
double ans=INF;
for(int i=1; i<=N; i++)
{
adj[i].clear();
for(int j=0; j<=K; j++)
{
if(A[i]==0 || i==1) ans=min(ans, dist[i][j]);
dist[i][j]=0;
}
}
if(ans>INF-100) ans=-1;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
2772 KB |
Correct. |
2 |
Correct |
22 ms |
2768 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
3108 KB |
Correct. |
2 |
Correct |
25 ms |
3124 KB |
Correct. |
3 |
Correct |
26 ms |
3096 KB |
Correct. |
4 |
Correct |
25 ms |
3112 KB |
Correct. |
5 |
Correct |
26 ms |
3104 KB |
Correct. |
6 |
Correct |
22 ms |
6484 KB |
Correct. |
7 |
Correct |
30 ms |
6364 KB |
Correct. |
8 |
Correct |
18 ms |
10196 KB |
Correct. |
9 |
Correct |
24 ms |
2776 KB |
Correct. |
10 |
Correct |
26 ms |
2756 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
3044 KB |
Correct. |
2 |
Correct |
22 ms |
3100 KB |
Correct. |
3 |
Correct |
23 ms |
3156 KB |
Correct. |
4 |
Correct |
26 ms |
2756 KB |
Correct. |
5 |
Correct |
28 ms |
2768 KB |
Correct. |
6 |
Correct |
7 ms |
5716 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
144 ms |
24824 KB |
Correct. |
2 |
Correct |
69 ms |
3088 KB |
Correct. |
3 |
Correct |
67 ms |
3028 KB |
Correct. |
4 |
Correct |
74 ms |
3020 KB |
Correct. |
5 |
Correct |
74 ms |
2748 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3164 KB |
Correct. |
2 |
Correct |
25 ms |
3156 KB |
Correct. |
3 |
Correct |
26 ms |
3140 KB |
Correct. |
4 |
Correct |
33 ms |
6528 KB |
Correct. |
5 |
Correct |
22 ms |
2644 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3112 KB |
Correct. |
2 |
Correct |
20 ms |
3084 KB |
Correct. |
3 |
Correct |
54 ms |
31888 KB |
Correct. |
4 |
Correct |
17 ms |
5460 KB |
Correct. |
5 |
Correct |
24 ms |
2768 KB |
Correct. |
6 |
Correct |
24 ms |
3156 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
3244 KB |
Correct. |
2 |
Correct |
23 ms |
3328 KB |
Correct. |
3 |
Correct |
566 ms |
39456 KB |
Correct. |
4 |
Correct |
206 ms |
11232 KB |
Correct. |
5 |
Correct |
351 ms |
18996 KB |
Correct. |
6 |
Correct |
166 ms |
10440 KB |
Correct. |
7 |
Correct |
236 ms |
11888 KB |
Correct. |
8 |
Correct |
149 ms |
4080 KB |
Correct. |
9 |
Correct |
85 ms |
3288 KB |
Correct. |
10 |
Correct |
72 ms |
3172 KB |
Correct. |
11 |
Correct |
118 ms |
3372 KB |
Correct. |
12 |
Correct |
95 ms |
3348 KB |
Correct. |
13 |
Correct |
82 ms |
3244 KB |
Correct. |
14 |
Correct |
260 ms |
20636 KB |
Correct. |
15 |
Correct |
237 ms |
7552 KB |
Correct. |
16 |
Correct |
87 ms |
3232 KB |
Correct. |
17 |
Correct |
92 ms |
3156 KB |
Correct. |
18 |
Correct |
86 ms |
3224 KB |
Correct. |
19 |
Correct |
148 ms |
3116 KB |
Correct. |
20 |
Correct |
8 ms |
2896 KB |
Correct. |
21 |
Correct |
10 ms |
3028 KB |
Correct. |
22 |
Correct |
14 ms |
3540 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
3240 KB |
Correct. |
2 |
Correct |
22 ms |
3328 KB |
Correct. |
3 |
Incorrect |
462 ms |
40716 KB |
Wrong Answer. |
4 |
Halted |
0 ms |
0 KB |
- |