QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#817373#2647. Environment-Friendly TravelSGColinAC ✓37ms12188kbC++202.0kb2024-12-16 22:00:062024-12-16 22:00:06

Judging History

你现在查看的是最新测评结果

  • [2024-12-16 22:00:06]
  • 评测
  • 测评结果:AC
  • 用时:37ms
  • 内存:12188kb
  • [2024-12-16 22:00:06]
  • 提交

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;
}

详细

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'