QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817373 | #2647. Environment-Friendly Travel | SGColin | AC ✓ | 37ms | 12188kb | C++20 | 2.0kb | 2024-12-16 22:00:06 | 2024-12-16 22:00:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read() {
int x = 0,f=1;
char c = getchar();
for (; !isdigit(c); c = getchar())if(c=='-')f=-f;
for (; isdigit(c); c = getchar()) x= x * 10 + (c ^ 48);
return x*f;
}
const int N=1005;
const int M=105;
int a[N][N];
int c[N][N];
int C[N];
int f[M][N];
int bx,by,ex,ey;
int x[N],y[N];
int len[N];
int dis(int xa,int ya,int xb,int yb)
{
return (ceil(sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))));
}
int main()
{
bx=read(),by=read();
ex=read(),ey=read();
int m=read();
C[0]=read();
int t=read();
for(int i=1;i<=t;i++){
C[i]=read();
}
int n=read();
for(int i=1;i<=n;i++){
x[i]=read(),y[i]=read();
int k=read();
for(int j=1;j<=k;j++){
int x,mx;
x=read()+1;mx=read();
a[i][x]=1;
c[i][x]=C[mx];
c[x][i]=C[mx];
a[x][i]=1;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]==1)a[i][j]=dis(x[i],y[i],x[j],y[j]);
else a[i][j]=m+1;
memset(f,127/3,sizeof(f));
for(int i=1;i<=n;i++){
int l=dis(bx,by,x[i],y[i]);
f[l][i]=C[0]*l;
}
int l=dis(bx,by,ex,ey);
if(l<=m)f[l][n+1]=C[0]*l;
for(int i=1;i<=n;i++)
len[i]=dis(x[i],y[i],ex,ey);
int maxm=C[0]*m;
for(int B=0;B<=m;B++){
for(int i=1;i<=n;i++){
if(B+len[i]>m)continue;
if(f[B][i]>maxm)continue;
f[B+len[i]][n+1]=min(f[B+len[i]][n+1],f[B][i]+C[0]*len[i]);
for(int j=1;j<=n;j++)
if(B+a[i][j]<=m){
f[B+a[i][j]][j]=min(f[B][i]+c[i][j]*a[i][j],f[B+a[i][j]][j]);
}
}
}
int ans=10005;
for(int i=0;i<=m;i++){
ans=min(f[i][n+1],ans);
}
if(ans==10005)puts("-1");
else printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7856kb
input:
1 1 10 2 12 100 2 10 50 3 2 3 2 1 1 2 2 5 5 1 2 1 9 3 0
output:
850
result:
ok single line: '850'
Test #2:
score: 0
Accepted
time: 0ms
memory: 6048kb
input:
1 1 9 8 10 100 1 1 2 3 5 1 1 1 7 3 1 0 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 8384kb
input:
3 5 6 3 4 100 2 80 70 4 3 1 3 1 1 3 1 2 1 6 7 2 2 2 3 2 8 2 2 1 2 3 2 11 7 0
output:
400
result:
ok single line: '400'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6248kb
input:
1 3 1 3 4 100 2 80 70 4 3 1 3 1 1 3 1 2 1 6 7 2 2 2 3 2 8 2 2 1 2 3 2 11 7 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7940kb
input:
10 2 2 2 12 100 2 10 40 4 2 4 2 1 1 3 2 4 6 1 2 1 9 6 1 3 1 10 4 0
output:
720
result:
ok single line: '720'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6240kb
input:
2 2 11 2 20 100 3 50 1 80 2 2 3 2 1 1 1 3 11 3 1 0 2
output:
209
result:
ok single line: '209'
Test #7:
score: 0
Accepted
time: 7ms
memory: 11896kb
input:
17 76 71 92 45 100 100 40 11 29 45 1 34 37 12 37 27 37 19 35 46 14 19 15 10 29 2 31 41 2 43 30 35 21 8 38 27 13 44 22 24 23 22 32 4 12 40 34 33 25 29 48 34 40 31 23 26 46 44 31 17 8 25 13 8 7 22 29 12 39 46 40 34 26 16 26 9 28 31 11 8 25 22 26 39 19 16 6 21 44 24 3 25 29 2 45 39 20 1 24 46 2 36 17 4...
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 6268kb
input:
0 0 0 12 15 100 2 1 10 8 0 2 2 2 1 1 2 0 4 1 3 2 8 4 1 3 1 0 6 1 4 2 0 8 2 5 1 6 2 3 10 1 7 1 0 10 1 7 2 0 12 0
output:
300
result:
ok single line: '300'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6452kb
input:
0 0 0 12 27 100 2 1 10 8 0 2 2 2 1 1 2 0 4 1 3 2 8 4 1 3 1 0 6 1 4 2 0 8 2 5 1 6 2 3 10 1 7 1 0 10 1 7 2 0 12 0
output:
268
result:
ok single line: '268'
Test #10:
score: 0
Accepted
time: 37ms
memory: 12188kb
input:
56 66 48 89 100 100 100 15 44 28 16 25 37 32 44 43 16 48 3 12 41 32 40 8 45 1 41 3 14 29 43 47 36 32 48 46 18 2 10 18 24 17 35 15 13 30 22 11 17 30 32 4 14 4 14 40 33 41 43 34 48 38 40 20 22 14 3 23 23 24 44 43 11 18 27 11 40 15 37 42 13 7 29 26 36 11 13 32 29 38 11 38 48 4 7 13 1 38 36 14 19 39 12 ...
output:
426
result:
ok single line: '426'
Test #11:
score: 0
Accepted
time: 3ms
memory: 12056kb
input:
0 0 56 52 100 100 10 1 2 3 4 5 6 7 8 9 10 1000 0 0 10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 9 0 2 9 0 3 9 0 4 9 0 5 9 0 6 9 0 7 9 0 8 9 0 9 9 0 10 9 19 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 11 1 12 2 13 3 14 4 15 5 16 6 17 7 18 8 19 9 20 10 9 17 0 8 17 0 7 17 0 6 17 0 5 17 0 4 17 0 3 17 0 2 17 0...
output:
4656
result:
ok single line: '4656'