XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#22607 #1079. 1-11D. JM的神庙逃亡 Accepted 100 777 ms 7916 K C++ 17 / 1.0 K Leohh 2020-02-13 15:25:44
显示原始代码 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 200005
#define INF 0x3f3f3f3f

using namespace std;

int n, m, a, b;
int dis[MAX_N];
bool vis[MAX_N];
vector<int> e[MAX_N];
queue<int> q;

bool bfs() {
    memset(dis, 0x3f, sizeof(dis));
    dis[a] = 0;
    if (a == b) {
        return true;
    }
    q.push(a), vis[a] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < e[x].size(); i++) {
            int t = e[x][i];
            if (!vis[t]) {
                dis[t] = dis[x] + 1;
                if (t == b) {
                    return true;
                }
                q.push(t), vis[t] = true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    int x, y;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    printf("%d\n", bfs() ? dis[b] + 1 : -1);
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：4 ms
内存：3464 KiB

输入文件（1.in） 

6 6 1 6
1 2
2 3
3 4
1 5
5 4
4 6

答案文件（1.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：6 ms
内存：3428 KiB

输入文件（2.in） 

4 3 1 4
1 2
2 3
1 3

答案文件（2.out） 

-1

用户输出 

-1

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：5 ms
内存：3492 KiB

输入文件（3.in） 

9 31 7 3
3 2
7 8
7 6
2 1
3 5
3 4
7 3
9 6
9 1
8 2
8 5
8 3
5 1
9 7
1 7
9 3
6 5
6 2
1 8
4 5
5 7
5 9
8 9
<33 bytes omitted>

答案文件（3.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：5 ms
内存：3428 KiB

输入文件（4.in） 

9 20 5 4
2 8
3 2
2 7
4 3
4 2
3 8
8 9
1 4
7 4
6 3
6 7
2 6
9 2
8 6
7 1
7 9
4 5
3 7
6 9
8 7

答案文件（4.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：6 ms
内存：3488 KiB

输入文件（5.in） 

9 8 9 5
8 5
9 3
2 9
1 2
7 2
6 8
4 1
2 8

答案文件（5.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：4 ms
内存：3488 KiB

输入文件（6.in） 

10 9 1 3
8 9
5 7
1 6
1 10
8 1
7 1
3 2
3 8
8 4

答案文件（6.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：4 ms
内存：3484 KiB

输入文件（7.in） 

12 21 7 11
7 9
4 6
6 11
7 11
2 7
12 10
12 7
5 3
1 12
11 12
4 12
7 8
9 1
9 12
3 12
8 4
1 10
5 7
8 2
9
<8 bytes omitted>

答案文件（7.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：4 ms
内存：3428 KiB

输入文件（8.in） 

11 11 2 4
5 9
9 11
5 8
9 3
10 1
9 10
10 8
4 2
10 7
6 8
7 1

答案文件（8.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：4 ms
内存：3424 KiB

输入文件（9.in） 

15 7 12 4
15 10
11 12
11 3
2 13
14 5
10 9
9 4

答案文件（9.out） 

-1

用户输出 

-1

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：6 ms
内存：3436 KiB

输入文件（10.in） 

13 9 12 4
9 1
9 2
1 2
1 6
5 11
10 1
4 7
12 11
7 11

答案文件（10.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：83 ms
内存：7448 KiB

输入文件（11.in） 

117224 195547 53440 106368
45993 67089
32498 45756
75092 58958
37615 95200
111884 9773
49730 99143
3
<2366924 bytes omitted>

答案文件（11.out） 

11

用户输出 

11

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：26 ms
内存：4892 KiB

输入文件（12.in） 

148425 61215 131631 74257
56343 1160
85619 99681
118948 23773
715 9349
127694 84850
54522 111432
555
<765069 bytes omitted>

答案文件（12.out） 

-1

用户输出 

-1

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：56 ms
内存：6104 KiB

输入文件（13.in） 

150724 129862 93020 113722
98339 133164
122267 372
43451 31705
119513 45945
89454 110229
37343 10158
<1626819 bytes omitted>

答案文件（13.out） 

-1

用户输出 

-1

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：88 ms
内存：7624 KiB

输入文件（14.in） 

144285 197897 98101 73161
103346 29386
94836 85444
69600 64976
56173 134340
21214 55410
98256 10490

<2465627 bytes omitted>

答案文件（14.out） 

13

用户输出 

13

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：73 ms
内存：7404 KiB

输入文件（15.in） 

109432 197520 91361 50079
4303 53737
77827 79082
12715 58750
2665 89721
73008 85932
74589 31977
1730
<2364035 bytes omitted>

答案文件（15.out） 

11

用户输出 

11

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：90 ms
内存：6804 KiB

输入文件（16.in） 

200000 199999 1 200000
158842 145192
29489 92185
180652 87805
105086 152681
194223 126601
131084 136
<2577701 bytes omitted>

答案文件（16.out） 

15203

用户输出 

15203

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：81 ms
内存：7696 KiB

输入文件（17.in） 

200000 199999 156495 127328
161312 5188
178299 77672
121736 52092
178299 164923
144187 178299
79068 
<2616702 bytes omitted>

答案文件（17.out） 

13095

用户输出 

13095

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：56 ms
内存：7916 KiB

输入文件（18.in） 

200000 199999 51655 81786
61304 139431
54934 61304
61304 19579
61304 43860
61304 169518
61304 138116
<2488809 bytes omitted>

答案文件（18.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：91 ms
内存：7720 KiB

输入文件（19.in） 

200000 200000 156389 39194
28695 142509
141378 154650
99870 42942
86312 188136
142924 197189
81309 9
<2577658 bytes omitted>

答案文件（19.out） 

15

用户输出 

15

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：85 ms
内存：7840 KiB

输入文件（20.in） 

200000 200000 66931 146912
103508 197023
97556 121274
197560 4386
130872 56172
44522 139416
75280 19
<2578607 bytes omitted>

答案文件（20.out） 

21

用户输出 

21

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号