QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211532#7404. Back and ForthSolitaryDream#AC ✓74ms8940kbC++172.1kb2023-10-12 17:56:062023-10-12 17:56:06

Judging History

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

  • [2023-10-12 17:56:06]
  • 评测
  • 测评结果：AC
  • 用时：74ms
  • 内存：8940kb
查看
  • [2023-10-12 17:56:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using tii=tuple<int,int,int>;

using pti=pair<int,tuple<int,int,int> >;

const int N=211;

int n,T,m,s,t;

int f[N][N],p[N];

int d[N][N][2];

priority_queue<pti,vector<pti>,greater<pti> >q;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=(i==j?0:1e9);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            f[u][v]=0;
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]+p[k]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=0;k<2;k++)
                    d[i][j][k]=1e8;
        d[s][s][0]=p[s];
        q.push({p[s],{s,s,0}});
        while(!q.empty())
        {
            auto [dis,Z]=q.top();
            q.pop();
            auto [x,y,z]=Z;
            if(dis!=d[x][y][z])
                continue;
            for(int u=1;u<=n;u++)
            {
                if(z==0)
                {
                    int nx=x;
                    int ny=u;
                    int nz=z^1;
                    if(d[nx][ny][nz]>d[x][y][z]+f[y][u]+p[u]*(u!=y))
                        d[nx][ny][nz]=d[x][y][z]+f[y][u]+p[u]*(u!=y),q.push({d[nx][ny][nz],{nx,ny,nz}});
                }
                else
                {
                    int nx=y;
                    int ny=u;
                    int nz=z^1;
                    if(d[nx][ny][nz]>d[x][y][z]+f[u][x]+f[y][u]+p[u]*(u!=y))
                    {
                        d[nx][ny][nz]=d[x][y][z]+f[u][x]+f[y][u]+p[u]*(u!=y),q.push({d[nx][ny][nz],{nx,ny,nz}});
                    }
                }
            }
        }
        int ans=d[t][t][0];
        if(ans>1e7)
            puts("-1");
        else
            printf("%d\n",ans);
    }
}
Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3812kb

input:

3
4 5 1 4
1 1 1 1
1 2
2 3
3 1
4 2
3 4
4 4 1 2
1 1 1 1
1 2
2 3
3 4
4 1
4 8 1 3
1 100 1 1
1 2
2 1
2 3
3 2
1 4
4 1
3 4
4 3

output:

4
4
3

result:

ok 3 number(s): "4 4 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

1
2 0 1 2
1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 4028kb

input:

10
20 40 5 16
2 1 1 1 2 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2
7 2
8 5
15 4
17 13
11 6
9 2
12 13
12 1
1 8
2 20
6 9
18 3
2 15
10 12
4 17
11 5
19 15
15 9
14 7
11 2
1 15
16 1
13 3
11 16
5 10
19 6
1 3
13 14
20 11
6 19
7 9
20 12
17 18
13 9
4 18
3 19
13 17
19 9
19 10
8 6
20 40 10 1
2 2 2 2 1 2 1 2 2 2 2 2 1 2 2 1 ...

output:

15
14
11
12
15
8
9
13
12
12

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 4048kb

input:

10
20 40 17 11
8 3 9 8 9 2 9 3 8 10 4 7 5 2 5 2 7 5 8 2
14 1
6 5
9 13
13 20
15 7
16 12
9 16
9 11
1 2
8 13
3 17
18 2
2 15
4 15
5 18
11 18
15 1
18 11
8 9
20 1
7 4
4 14
1 8
5 19
13 12
5 3
12 8
7 14
3 18
2 19
11 13
12 6
20 10
20 6
19 7
10 20
17 16
10 19
19 3
15 14
20 40 20 2
6 2 3 1 8 3 9 8 5 2 7 8 2 5 ...

output:

50
32
30
52
42
45
34
55
40
55

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 3932kb

input:

10
20 40 18 6
66 8 72 32 88 52 22 28 50 62 1 73 83 81 14 82 50 90 90 87
13 10
11 18
16 12
20 8
11 15
3 12
15 2
14 13
17 7
2 5
18 3
4 2
15 4
2 15
7 9
2 1
17 14
14 18
15 8
16 1
4 17
14 19
5 8
20 11
7 5
19 16
6 10
1 4
14 20
5 6
12 13
8 13
2 18
10 17
9 20
12 15
1 5
7 6
16 18
9 3
20 40 10 20
46 66 84 50 ...

output:

525
239
429
400
328
517
229
391
664
376

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 8ms
memory: 4200kb

input:

4
50 100 16 46
2 3 3 1 2 1 2 5 2 5 5 5 5 1 3 1 1 5 2 1 3 5 5 3 3 1 4 5 1 3 1 5 3 4 1 2 1 4 4 1 1 3 5 1 2 5 3 3 3 3
28 1
7 18
3 17
48 5
27 42
18 49
6 5
26 27
48 25
15 21
41 15
32 31
39 30
30 22
23 2
35 9
19 37
44 22
50 43
14 46
26 3
24 2
37 23
25 30
39 19
36 41
45 17
31 50
26 38
14 38
30 3
3 10
13 7
...

output:

36
38
23
36

result:

ok 4 number(s): "36 38 23 36"

Test #7:

score: 0
Accepted
time: 66ms
memory: 8940kb

input:

1
200 300 169 170
2 1 2 1 1 2 1 1 2 2 2 2 2 1 2 2 2 1 1 2 2 2 2 2 2 1 2 1 2 1 2 2 2 2 2 1 2 2 2 1 1 2 2 2 1 2 2 2 2 2 1 1 2 2 1 2 2 2 1 2 2 2 1 2 1 1 1 2 2 1 2 2 2 2 2 1 2 2 2 2 1 1 2 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 2 1 1 1 1 2 2 1 2 2 2 1 1 1 2 1 2 1 1 1 1 1 1 1 2 2 1 2 2 1 1 2 1 2 2 2 1 1 1 2 1 2 1 ...

output:

30

result:

ok 1 number(s): "30"

Test #8:

score: 0
Accepted
time: 74ms
memory: 8372kb

input:

1
200 300 100 39
11 5 9 6 5 1 7 4 3 3 13 4 5 12 8 9 2 1 5 4 6 7 10 12 12 4 13 1 7 14 1 8 15 10 3 3 11 15 11 8 4 5 9 15 7 13 12 13 1 14 9 15 5 1 7 2 3 5 6 7 12 10 9 8 12 11 15 15 8 10 9 12 14 1 1 10 3 15 10 7 2 2 10 10 9 13 15 10 7 3 8 1 15 12 3 14 13 15 11 10 3 1 8 4 9 13 5 1 8 15 10 11 15 6 5 1 10 ...

output:

264

result:

ok 1 number(s): "264"

Test #9:

score: 0
Accepted
time: 61ms
memory: 5696kb

input:

1
200 400 90 131
2 1 1 1 2 1 2 2 1 2 2 2 1 2 1 1 2 1 2 2 1 2 1 2 2 2 1 2 2 1 2 2 1 2 1 2 1 1 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 1 1 2 1 2 2 1 1 1 1 1 2 1 1 2 1 2 2 1 2 2 1 1 2 1 2 1 2 2 1 2 2 1 2 1 2 1 1 2 1 2 2 2 2 1 2 1 2 2 1 1 2 1 1 2 1 2 2 2 1 2 2 2 2 2 1 1 1 2 1 1 1 1 1 2 2 2 1 2 1 2 1 1 1 1 2 1 2...

output:

21

result:

ok 1 number(s): "21"

Test #10:

score: 0
Accepted
time: 68ms
memory: 8252kb

input:

1
200 400 196 119
15 11 14 6 9 12 12 1 13 2 5 9 15 10 11 12 15 13 9 10 15 1 15 2 2 10 15 3 5 3 15 13 13 1 1 13 10 10 11 1 12 7 4 3 8 7 13 13 5 13 1 3 1 1 1 4 10 10 6 13 9 7 1 13 13 7 7 10 14 7 9 2 3 8 1 2 15 1 5 11 14 15 12 5 15 11 12 14 10 14 14 14 15 7 5 1 10 7 14 12 9 5 7 9 8 10 2 5 5 15 14 9 4 3...

output:

102

result:

ok 1 number(s): "102"

Test #11:

score: 0
Accepted
time: 56ms
memory: 5736kb

input:

1
200 800 91 57
2 2 2 1 2 2 1 2 1 2 2 2 1 1 2 1 1 2 1 1 1 2 2 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 2 2 1 1 1 2 1 2 1 1 1 2 2 2 1 1 1 2 1 1 2 1 2 2 2 1 2 2 2 2 1 1 1 1 2 2 2 2 2 1 2 1 1 2 1 1 1 1 2 2 2 2 2 1 1 1 1 2 1 2 2 1 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 2 2 1 2 2 2 1 2 1 1 2 1 1 1 2 1 2 2 1 2 1 1 1 1 2 1 ...

output:

11

result:

ok 1 number(s): "11"

Test #12:

score: 0
Accepted
time: 62ms
memory: 5932kb

input:

1
200 800 26 27
7 5 1 8 14 11 5 5 15 15 3 2 6 2 7 7 4 2 4 5 9 1 13 15 11 2 13 10 10 12 3 4 2 6 1 1 10 11 7 2 8 13 13 10 14 4 14 4 11 9 11 6 14 10 4 14 12 10 10 2 8 6 10 12 13 13 12 15 14 10 15 4 9 8 9 1 15 4 11 15 9 9 12 5 4 3 10 1 2 10 10 13 1 6 8 8 3 5 13 6 3 4 5 11 1 1 5 5 14 3 1 10 12 9 3 7 14 3...

output:

55

result:

ok 1 number(s): "55"

Test #13:

score: 0
Accepted
time: 50ms
memory: 5932kb

input:

1
200 1600 91 175
2 1 2 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 2 2 2 1 1 1 1 2 2 1 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 1 2 2 2 1 2 2 1 2 1 2 2 1 2 2 2 1 1 2 1 1 1 2 1 1 1 2 1 2 2 1 1 2 2 1 2 2 1 2 1 1 1 1 1 1 2 2 2 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 2 1 1 2 1 2 2 1 1 ...

output:

8

result:

ok 1 number(s): "8"

Test #14:

score: 0
Accepted
time: 56ms
memory: 5720kb

input:

1
200 1600 73 167
1 4 6 11 1 13 4 5 7 4 12 4 1 8 10 10 4 2 1 15 1 6 7 13 14 6 11 11 13 15 9 5 14 12 1 14 3 15 2 11 4 3 5 11 8 15 6 2 1 5 8 15 3 7 1 5 6 14 11 13 9 2 3 14 5 3 3 2 5 14 5 7 6 8 4 10 8 13 3 9 7 3 9 7 7 12 4 12 7 9 5 5 1 13 10 9 4 3 3 2 12 12 12 7 4 5 2 11 12 9 11 3 7 14 9 8 4 11 11 7 7 ...

output:

37

result:

ok 1 number(s): "37"

Test #15:

score: 0
Accepted
time: 52ms
memory: 5828kb

input:

1
200 3200 36 187
3 8 13 7 8 3 2 9 12 8 15 5 8 4 5 13 12 15 3 2 6 8 9 12 14 7 10 15 7 13 6 10 6 2 12 9 8 2 13 13 3 13 3 13 8 8 11 3 7 12 6 6 14 8 11 5 5 6 10 12 3 1 8 6 14 6 11 12 4 10 6 4 4 7 8 9 1 11 11 9 9 5 4 10 4 12 5 12 15 3 15 4 6 14 14 8 13 15 7 11 1 6 10 5 2 1 5 2 1 5 8 2 12 8 13 12 11 13 1...

output:

22

result:

ok 1 number(s): "22"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-30 18:55:55 | OpenSource Project