#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
constexpr int N=1e5+5,KX=67;
constexpr double INF=1e99;
int n,m,kk,h,ty[N];
vector<pii> g[N];
bool reach[N];
double f[N][KX+3][2];
vector<int> st;
inline void bfsinit(int s){
queue<int> q;
memset(reach,0,n*sizeof(bool));
reach[s]=true,
q.emplace(s);
while(!q.empty()){
int u{q.front()};q.pop();
for(auto e:g[u]){
int v{e.first};
if(!reach[v]){
reach[v]=true,
q.emplace(v);
}
}
}
}
inline void dijx(){
struct Q{
int u,d;
double dis;
bool div2;
Q(){}
Q(int u,int d,double ds,bool d2):
u{u},d{d},dis{ds},div2{d2}{}
inline bool operator<(const Q &b)const{
return dis>b.dis;
}
};
queue<Q> q;
static bool inq[N][KX+3][2];
for(int i{0};i<n;++i){
for(int j{0};j<=kk;++j){
f[i][j][0]=f[i][j][1]=INF;
inq[i][j][0]=inq[i][j][1]=false;
}
}
for(int s:st){
f[s][0][0]=0.0;
q.emplace(s,0,f[s][0][0],false);
inq[s][0][0]=true;
}
while(!q.empty()){
auto t=q.front();q.pop();
inq[t.u][t.d][t.div2]=false;
double tdis=f[t.u][t.d][t.div2];
if(t.d<kk&&!t.div2&&ty[t.u]==2&&tdis/2.0<f[t.u][t.d+1][1]){
f[t.u][t.d+1][1]=tdis/2.0;
if(!inq[t.u][t.d+1][1]){
q.emplace(t.u,t.d+1,f[t.u][t.d+1][1],true);
inq[t.u][t.d+1][1]=true;
}
}
for(pii e:g[t.u]){
int v{e.first},w{e.second};
if(tdis+w<f[v][t.d][0]){
f[v][t.d][0]=tdis+w;
if(!inq[v][t.d][0]){
q.emplace(v,t.d,f[v][t.d][0],false);
inq[v][t.d][0]=true;
}
}
}
}
}
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,kk=K,h=H;
kk=min(kk,KX);
for(int i{0};i<n;++i){
ty[i]=arr[i];
g[i].clear();
}
for(int i{0};i<m;++i){
int u{x[i]},v{y[i]},w{c[i]};
if(u!=h) g[u].emplace_back(v,w);
if(v!=h) g[v].emplace_back(u,w);
}
bfsinit(0);
if(!reach[h]) return -1;
for(int i{0};i<n;++i){
if(i==0||(ty[i]==0&&reach[i])){
st.emplace_back(i);
}
}
dijx();
double ans{INF};
for(int i{0};i<=kk;++i){
ans=min({ans,f[h][i][0],f[h][i][1]});
}
st.clear();
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
2912 KB |
Correct. |
2 |
Correct |
18 ms |
3112 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
4348 KB |
Correct. |
2 |
Correct |
21 ms |
4964 KB |
Correct. |
3 |
Correct |
21 ms |
4892 KB |
Correct. |
4 |
Correct |
21 ms |
4892 KB |
Correct. |
5 |
Correct |
23 ms |
4940 KB |
Correct. |
6 |
Correct |
22 ms |
16244 KB |
Correct. |
7 |
Correct |
29 ms |
16136 KB |
Correct. |
8 |
Correct |
20 ms |
28668 KB |
Correct. |
9 |
Correct |
21 ms |
3540 KB |
Correct. |
10 |
Correct |
20 ms |
3628 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
4908 KB |
Correct. |
2 |
Correct |
21 ms |
4788 KB |
Correct. |
3 |
Correct |
20 ms |
4924 KB |
Correct. |
4 |
Correct |
24 ms |
3160 KB |
Correct. |
5 |
Correct |
21 ms |
3668 KB |
Correct. |
6 |
Correct |
9 ms |
13464 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
80896 KB |
Correct. |
2 |
Correct |
139 ms |
4900 KB |
Correct. |
3 |
Correct |
125 ms |
5000 KB |
Correct. |
4 |
Correct |
135 ms |
5008 KB |
Correct. |
5 |
Correct |
104 ms |
3580 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
4948 KB |
Correct. |
2 |
Correct |
19 ms |
4856 KB |
Correct. |
3 |
Correct |
19 ms |
4860 KB |
Correct. |
4 |
Correct |
24 ms |
16332 KB |
Correct. |
5 |
Correct |
17 ms |
3556 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
4940 KB |
Correct. |
2 |
Correct |
19 ms |
4916 KB |
Correct. |
3 |
Correct |
40 ms |
9548 KB |
Correct. |
4 |
Correct |
16 ms |
11008 KB |
Correct. |
5 |
Correct |
20 ms |
3712 KB |
Correct. |
6 |
Correct |
19 ms |
4604 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
4964 KB |
Correct. |
2 |
Correct |
24 ms |
4084 KB |
Correct. |
3 |
Correct |
383 ms |
130392 KB |
Correct. |
4 |
Correct |
133 ms |
33348 KB |
Correct. |
5 |
Correct |
901 ms |
56936 KB |
Correct. |
6 |
Correct |
391 ms |
22092 KB |
Correct. |
7 |
Correct |
133 ms |
35856 KB |
Correct. |
8 |
Correct |
114 ms |
9028 KB |
Correct. |
9 |
Correct |
121 ms |
5048 KB |
Correct. |
10 |
Correct |
115 ms |
4940 KB |
Correct. |
11 |
Correct |
129 ms |
6240 KB |
Correct. |
12 |
Correct |
141 ms |
4816 KB |
Correct. |
13 |
Correct |
143 ms |
4976 KB |
Correct. |
14 |
Correct |
166 ms |
65004 KB |
Correct. |
15 |
Correct |
152 ms |
21068 KB |
Correct. |
16 |
Correct |
136 ms |
4940 KB |
Correct. |
17 |
Correct |
161 ms |
5196 KB |
Correct. |
18 |
Correct |
144 ms |
5200 KB |
Correct. |
19 |
Correct |
395 ms |
5988 KB |
Correct. |
20 |
Correct |
10 ms |
2808 KB |
Correct. |
21 |
Correct |
10 ms |
3348 KB |
Correct. |
22 |
Correct |
19 ms |
4428 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
476 ms |
4720 KB |
Correct. |
2 |
Correct |
67 ms |
4252 KB |
Correct. |
3 |
Correct |
231 ms |
135180 KB |
Correct. |
4 |
Correct |
209 ms |
13212 KB |
Correct. |
5 |
Execution timed out |
3071 ms |
60712 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |