XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#13481 #1079. 1-11D. JM的神庙逃亡 Accepted 100 1437 ms 8292 K C++ / 796 B 电类816 叶雨轩 2019-07-06 23:18:09
显示原始代码 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 1000005
using namespace std;

vector<int> a[200005];
queue<int> q;
int visit[200005];
int n, m, s, f;

int bfs(int x) {
    if (q.empty())
        return 0;
    for (int i = 0; i < a[x].size(); i++) {
        if (!visit[a[x][i]] || visit[a[x][i]] > visit[x] + 1) {
            if (a[x][i] == f) {
                visit[f] = visit[x] + 1;
                while (!q.empty()) q.pop();
                return 0;
            }
            q.push(a[x][i]);
            visit[a[x][i]] = visit[x] + 1;
        }
    }
    q.pop();
    bfs(q.front());
    return 0;
}

int main() {
    cin >> n >> m >> s >> f;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    visit[s] = 1;
    q.push(s);
    bfs(s);
    if (!visit[f])
        cout << -1;
    else
        cout << visit[f];
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：7 ms
内存：2736 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
用时：8 ms
内存：2696 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
用时：6 ms
内存：2708 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
用时：9 ms
内存：2704 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
用时：7 ms
内存：2688 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
用时：7 ms
内存：2704 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
用时：6 ms
内存：2692 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
用时：7 ms
内存：2704 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
用时：6 ms
内存：2708 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
用时：7 ms
内存：2736 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
用时：139 ms
内存：7528 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
用时：48 ms
内存：4036 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
用时：98 ms
内存：5272 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
用时：160 ms
内存：8292 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
用时：158 ms
内存：7136 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
用时：161 ms
内存：7028 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
用时：155 ms
内存：8020 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
用时：125 ms
内存：7724 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
用时：168 ms
内存：7684 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
用时：155 ms
内存：7784 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号