#include <algorithm>
#include <queue>
const int Nx=100010;
const double inf=1e24;
int n,m,k,h,ab[Nx];
struct edge{int to,nex,val,typ;};
edge a[300*Nx];
int head[75*Nx],cnt;
void add(int u,int v,int w,int t)
{
a[++cnt]=edge{v,head[u],w,t};
head[u]=cnt;
}
struct node
{
int idx;double val;
bool operator < (const node &x) const
{
if(idx/n!=x.idx/n)
return idx/n>x.idx/n;
return val>x.val;
}
};
int id(int x,int lev){return x+lev*n;}
void find_zpair(int p)
{
ab[p]=1;
int i;
for(i=head[p];i;i=a[i].nex)
{
if(ab[a[i].to]==0&&p!=h)
find_zpair(a[i].to);
}
}
double dis[75*Nx];
int fin[75*Nx];
void clear_all()
{
int i;
for(i=0;i<n;i++)
ab[i]=0;
for(i=0;i<=(k+1)*n+1;i++)
head[i]=dis[i]=fin[i]=0;
cnt=n=m=k=h=0;
}
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)
{
clear_all();
n=N,m=M,k=K,h=H;
int i,j,now,fx,fy;
for(i=0;i<M;i++)
{
add(X[i],Y[i],C[i],1);
add(Y[i],X[i],C[i],1);
}
find_zpair(0);
if(ab[H]==0)
return -1;
for(i=0;i<=N;i++)
head[i]=0;
cnt=0;
for(i=0;i<M;i++)
{
for(j=0;j<=K;j++)
{
if(X[i]!=H)
add(id(X[i],j),id(Y[i],j),C[i],1);
if(Y[i]!=H)
add(id(Y[i],j),id(X[i],j),C[i],1);
if(j!=K&&X[i]!=H&&arr[Y[i]]==2)
add(id(X[i],j),id(Y[i],j+1),C[i],2);
if(j!=K&&Y[i]!=H&&arr[X[i]]==2)
add(id(Y[i],j),id(X[i],j+1),C[i],2);
}
}
for(i=0;i<=(K+1)*N+1;i++)
dis[i]=inf,fin[i]=0;
std::priority_queue<node> hea;
for(i=0;i<N;i++)
{
if(arr[i]==0&&ab[i]==1)
{
hea.push(node{i,0});
dis[i]=0;
}
}
hea.push(node{0,0});
dis[0]=0;
while(hea.size())
{
node ax=hea.top();
hea.pop();
now=ax.idx;
if(fin[now])
continue;
fin[now]=1;
for(i=head[now];i;i=a[i].nex)
{
if(dis[a[i].to]>(dis[now]+a[i].val)/a[i].typ)
{
dis[a[i].to]=(dis[now]+a[i].val)/a[i].typ;
if(!fin[a[i].to])
hea.push(node{a[i].to,dis[a[i].to]});
}
}
}
double ans=inf;
for(i=0;i<=K;i++)
ans=std::min(ans,dis[id(H,i)]);
return ans;
}
Compilation message
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:50:14: warning: unused variable 'fx' [-Wunused-variable]
50 | int i,j,now,fx,fy;
| ^~
cyberland.cpp:50:17: warning: unused variable 'fy' [-Wunused-variable]
50 | int i,j,now,fx,fy;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
7004 KB |
Correct. |
2 |
Correct |
14 ms |
7000 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
7516 KB |
Correct. |
2 |
Correct |
26 ms |
7772 KB |
Correct. |
3 |
Correct |
25 ms |
7772 KB |
Correct. |
4 |
Correct |
27 ms |
7772 KB |
Correct. |
5 |
Correct |
26 ms |
7764 KB |
Correct. |
6 |
Correct |
25 ms |
21124 KB |
Correct. |
7 |
Correct |
31 ms |
21116 KB |
Correct. |
8 |
Correct |
16 ms |
36700 KB |
Correct. |
9 |
Correct |
28 ms |
7548 KB |
Correct. |
10 |
Correct |
24 ms |
7512 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
7760 KB |
Correct. |
2 |
Correct |
26 ms |
7760 KB |
Correct. |
3 |
Correct |
24 ms |
6928 KB |
Correct. |
4 |
Correct |
26 ms |
7568 KB |
Correct. |
5 |
Correct |
25 ms |
7512 KB |
Correct. |
6 |
Correct |
8 ms |
18264 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
131 ms |
110932 KB |
Correct. |
2 |
Correct |
123 ms |
7760 KB |
Correct. |
3 |
Correct |
110 ms |
7724 KB |
Correct. |
4 |
Correct |
118 ms |
7764 KB |
Correct. |
5 |
Correct |
77 ms |
7540 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
7512 KB |
Correct. |
2 |
Correct |
30 ms |
7772 KB |
Correct. |
3 |
Correct |
25 ms |
7800 KB |
Correct. |
4 |
Correct |
30 ms |
21584 KB |
Correct. |
5 |
Correct |
19 ms |
7256 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
7772 KB |
Correct. |
2 |
Correct |
19 ms |
7516 KB |
Correct. |
3 |
Correct |
19 ms |
12928 KB |
Correct. |
4 |
Correct |
16 ms |
22140 KB |
Correct. |
5 |
Correct |
20 ms |
7516 KB |
Correct. |
6 |
Correct |
21 ms |
7812 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
124 ms |
7644 KB |
Correct. |
2 |
Correct |
21 ms |
11096 KB |
Correct. |
3 |
Correct |
359 ms |
93520 KB |
Correct. |
4 |
Correct |
227 ms |
31824 KB |
Correct. |
5 |
Correct |
556 ms |
127432 KB |
Correct. |
6 |
Correct |
306 ms |
107216 KB |
Correct. |
7 |
Correct |
225 ms |
29292 KB |
Correct. |
8 |
Correct |
203 ms |
12884 KB |
Correct. |
9 |
Correct |
105 ms |
7708 KB |
Correct. |
10 |
Correct |
90 ms |
7760 KB |
Correct. |
11 |
Correct |
211 ms |
8764 KB |
Correct. |
12 |
Correct |
113 ms |
7664 KB |
Correct. |
13 |
Correct |
114 ms |
7664 KB |
Correct. |
14 |
Correct |
194 ms |
27808 KB |
Correct. |
15 |
Correct |
207 ms |
15716 KB |
Correct. |
16 |
Correct |
104 ms |
7796 KB |
Correct. |
17 |
Correct |
128 ms |
7760 KB |
Correct. |
18 |
Correct |
111 ms |
7704 KB |
Correct. |
19 |
Correct |
300 ms |
8788 KB |
Correct. |
20 |
Correct |
7 ms |
6488 KB |
Correct. |
21 |
Correct |
8 ms |
6748 KB |
Correct. |
22 |
Correct |
22 ms |
17244 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
665 ms |
1115116 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |