QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#58045#3711. Floyd-WarshallMaMengQiRE 7ms22436kbC++141.4kb2022-10-24 15:01:092022-10-24 15:01:11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0
1
2

result:

ok 3 number(s): "0 1 2"

Test #2:

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

input:

1 2 1
1 1
1 1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 14968kb

input:

5 7 10
5 3
1 2
4 1
2 5
3 4
2 2
1 3
5 5
4 5
3 2
4 4
5 3
3 5
2 4
4 2
5 3
4 2

output:

0
2
2
0
1
1
2
2
1
2

result:

ok 10 numbers

Test #4:

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

input:

5 8 10
5 1
1 3
4 5
2 3
1 5
4 2
2 2
2 3
2 1
2 3
4 5
1 1
2 2
5 3
3 5
3 4
4 5
1 1

output:

2
1
1
0
0
2
2
2
1
0

result:

ok 10 numbers

Test #5:

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

input:

5 8 10
4 1
5 2
3 5
3 1
5 1
5 1
4 2
2 5
3 1
3 2
2 1
3 2
3 3
1 5
4 5
4 3
4 3
2 5

output:

1
2
2
2
0
1
2
2
2
1

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 16596kb

input:

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

output:

0
1
1
1
1
1
0
2
1
1

result:

ok 10 numbers

Test #7:

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

input:

5 8 10
2 3
5 3
1 4
3 1
5 5
1 2
2 5
1 2
3 5
2 5
3 5
3 2
3 2
2 5
2 4
1 2
2 2
5 2

output:

1
1
1
1
1
1
2
1
0
1

result:

ok 10 numbers

Test #8:

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

input:

5 7 10
1 3
4 1
4 2
5 4
4 1
5 4
3 5
2 3
1 1
5 4
4 3
1 1
3 3
3 1
2 3
5 5
2 5

output:

3
0
1
2
0
0
1
3
0
2

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 14980kb

input:

5 8 10
1 2
1 5
4 1
2 3
4 5
3 3
4 1
2 5
5 1
5 3
3 4
1 5
1 4
3 5
1 4
1 3
5 4
2 4

output:

1
2
3
1
1
2
1
2
1
2

result:

ok 10 numbers

Test #10:

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

input:

5 7 10
5 2
2 1
5 3
3 4
1 5
1 1
5 3
4 5
3 1
3 1
3 1
2 1
2 1
5 1
4 4
5 3
3 2

output:

2
2
2
2
1
1
1
0
1
2

result:

ok 10 numbers

Test #11:

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

input:

5 8 10
1 5
3 5
2 5
1 4
4 1
3 3
5 5
5 2
1 5
2 3
2 2
3 4
3 2
1 1
5 3
3 4
5 4
2 4

output:

1
2
0
3
2
0
1
3
2
3

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 5ms
memory: 15780kb

input:

5 7 10
5 1
5 3
2 5
4 2
3 3
3 2
2 2
1 5
2 3
2 2
5 4
3 3
2 5
5 5
3 4
2 2
5 5

output:

1
1
0
2
0
1
0
2
0
0

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 4ms
memory: 16588kb

input:

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

output:

2
2
4
2
1
1
3
1
1
2

result:

ok 10 numbers

Test #14:

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

input:

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

output:

4
3
0
4
1
1
0
3
1
0

result:

ok 10 numbers

Test #15:

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

input:

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

output:

2
2
2
1
2
3
3
1
0
2

result:

ok 10 numbers

Test #16:

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

input:

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

output:

0
1
3
1
3
2
3
0
0
4

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 1ms
memory: 20300kb

input:

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

output:

2
3
1
0
2
1
0
3
3
1

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 1ms
memory: 19880kb

input:

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

output:

5
0
0
5
1
3
1
2
1
1

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 5ms
memory: 20124kb

input:

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

output:

1
2
1
4
2
3
1
1
2
3

result:

ok 10 numbers

Test #20:

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

input:

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

output:

1
2
1
0
2
1
2
3
1
1

result:

ok 10 numbers

Test #21:

score: 0
Accepted
time: 4ms
memory: 20040kb

input:

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

output:

4
3
2
2
1
0
2
0
3
2

result:

ok 10 numbers

Test #22:

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

input:

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

output:

1
2
0
2
2
3
1
2
1
2

result:

ok 10 numbers

Test #23:

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

input:

100 154 1000
35 12
42 72
44 83
47 99
100 98
27 73
83 25
78 91
44 2
67 22
58 12
78 76
58 67
77 45
62 77
75 31
53 62
48 19
69 13
12 90
48 5
60 37
99 45
63 29
46 32
65 23
94 86
80 17
89 73
55 91
46 57
81 20
26 85
28 38
33 63
67 89
46 12
18 77
86 73
42 39
66 55
47 33
24 20
4 83
83 96
54 46
88 1
37 36
42...

output:

7
4
4
2
4
6
5
5
4
3
3
4
4
5
3
6
5
6
3
6
4
5
1
3
6
4
3
5
6
3
7
5
4
0
3
6
5
3
3
7
3
5
2
4
3
6
2
3
4
5
3
4
3
5
4
4
5
3
3
6
5
2
4
4
3
4
4
4
2
5
5
2
5
4
4
2
6
6
8
6
3
5
5
4
5
4
6
5
4
5
2
4
4
6
4
5
5
5
4
6
6
5
5
2
4
4
7
4
2
6
3
7
5
4
2
6
6
3
5
6
6
5
5
5
3
5
5
3
4
5
4
3
5
5
1
2
6
5
5
7
4
4
7
6
5
2
5
5
2
4
...

result:

ok 1000 numbers

Test #24:

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

input:

100 189 1000
79 57
24 34
21 66
39 58
82 38
67 63
12 48
99 13
3 20
11 71
40 25
62 33
66 88
38 54
33 99
53 18
90 71
44 53
40 46
23 87
62 98
6 26
83 52
3 47
17 50
21 12
18 82
14 8
2 24
59 3
63 92
63 51
84 70
51 29
59 8
57 100
58 95
56 37
73 30
54 94
22 81
62 76
92 80
46 32
6 34
67 49
53 19
24 44
89 42
...

output:

3
4
5
4
3
4
5
2
5
3
4
5
3
4
4
1
5
5
6
3
4
3
0
4
4
3
3
4
4
5
4
1
3
3
4
4
3
4
2
2
3
5
4
1
4
3
2
3
2
4
3
4
4
3
3
4
4
4
1
5
5
2
5
4
5
3
2
4
4
3
4
3
3
4
4
3
4
3
4
4
5
4
3
3
2
4
5
4
3
4
3
0
4
2
3
3
5
5
4
3
3
5
4
3
3
3
4
3
3
4
5
2
4
4
4
3
3
3
4
2
2
4
5
5
4
4
4
3
3
4
5
1
2
5
5
5
2
3
3
2
3
4
3
4
3
5
5
5
4
4
...

result:

ok 1000 numbers

Test #25:

score: 0
Accepted
time: 7ms
memory: 21904kb

input:

100 125 1000
24 11
1 87
86 42
27 14
64 74
23 61
53 63
16 36
57 38
60 11
25 31
41 90
74 5
99 66
3 25
24 9
18 84
52 83
7 88
33 79
81 79
68 14
63 68
47 65
72 64
73 2
43 86
49 91
27 79
67 10
68 39
41 82
49 54
71 28
97 57
39 19
62 70
87 97
56 87
62 44
71 12
86 7
68 52
93 82
28 72
83 56
10 28
22 61
40 80
...

output:

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

result:

ok 1000 numbers

Test #26:

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

input:

100 156 1000
72 69
79 45
63 29
15 69
46 17
62 55
83 86
25 58
11 60
5 64
3 48
24 51
91 26
52 86
69 43
2 5
55 84
52 12
82 26
40 76
95 64
23 11
42 76
91 87
42 73
17 91
67 82
87 74
48 26
79 21
90 75
19 17
10 43
99 19
31 14
38 35
78 46
21 54
39 32
70 91
27 42
14 41
28 24
44 31
51 6
96 68
75 37
12 69
88 2...

output:

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

result:

ok 1000 numbers

Test #27:

score: 0
Accepted
time: 1ms
memory: 21548kb

input:

100 191 1000
20 14
57 98
36 100
3 29
29 57
6 46
24 1
42 80
65 78
50 12
81 57
95 12
7 47
13 99
40 74
72 96
87 93
60 42
57 63
59 73
14 45
77 100
26 87
27 5
97 91
69 84
95 74
22 64
69 81
83 25
95 10
96 40
64 20
65 58
20 58
89 17
51 6
26 85
86 42
83 69
38 84
100 88
86 81
70 44
16 79
40 46
10 77
47 56
19...

output:

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

result:

ok 1000 numbers

Test #28:

score: 0
Accepted
time: 5ms
memory: 21472kb

input:

100 127 1000
61 68
30 52
4 83
91 88
11 100
46 36
57 24
59 95
24 4
2 61
67 66
78 69
15 68
74 19
6 100
47 87
31 6
61 76
32 1
65 74
28 34
36 4
13 7
71 19
68 13
24 69
16 66
60 55
94 36
92 36
8 49
78 71
29 5
42 21
99 7
6 73
97 92
81 58
9 38
89 96
39 95
66 15
72 59
33 35
89 78
29 82
5 55
97 93
94 2
31 40
...

output:

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

result:

ok 1000 numbers

Test #29:

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

input:

100 162 1000
5 13
8 13
81 63
79 44
97 48
97 30
94 47
76 21
86 22
43 1
44 76
58 26
24 90
76 14
21 82
64 7
69 2
3 38
84 67
39 19
90 93
97 18
15 37
22 27
64 55
36 66
98 42
15 83
4 43
29 84
60 7
94 90
70 12
37 60
93 92
5 68
11 18
96 83
5 39
91 25
86 50
36 31
11 16
37 89
70 68
95 2
41 44
55 17
71 36
62 9...

output:

6
5
4
6
5
2
1
4
4
2
4
5
3
4
4
4
5
4
3
3
5
6
3
1
2
5
4
6
4
6
3
3
6
3
5
5
3
4
6
3
6
4
5
3
7
3
3
5
2
4
5
2
4
5
5
3
4
5
4
5
3
3
4
5
4
1
4
4
2
3
4
3
6
4
5
6
3
5
6
5
4
0
5
2
3
6
0
5
6
4
3
4
3
4
1
4
2
6
2
5
4
4
5
3
4
3
4
4
2
4
4
3
3
5
6
5
5
7
1
2
4
5
2
5
2
3
0
3
2
4
2
2
3
4
3
0
4
1
4
3
4
4
4
2
5
5
3
2
5
3
...

result:

ok 1000 numbers

Test #30:

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

input:

100 193 1000
49 75
85 67
54 42
68 3
76 88
41 16
28 58
97 36
36 40
92 54
22 93
41 87
44 7
92 52
50 40
100 73
100 19
69 35
78 76
91 71
61 96
45 82
85 30
51 55
89 40
20 52
64 58
36 38
8 47
34 23
42 38
60 71
90 11
63 9
79 7
16 39
46 78
79 40
13 89
44 60
9 93
4 95
26 54
54 1
31 78
93 18
93 78
80 90
41 45...

output:

2
2
4
2
3
4
2
5
3
3
2
3
5
3
3
2
4
5
4
3
3
4
4
2
4
4
4
3
3
4
2
0
2
4
5
4
5
0
2
4
5
6
4
2
5
5
4
4
4
5
3
4
3
4
4
4
4
3
4
4
4
3
3
4
4
4
4
2
3
4
2
3
2
4
5
4
2
3
2
4
5
2
2
4
3
4
2
3
4
4
3
1
4
4
3
4
3
1
3
3
2
4
2
3
2
3
3
4
4
4
5
5
3
0
6
4
4
4
5
3
5
3
2
4
3
4
1
3
3
3
4
3
4
2
2
3
4
4
3
2
4
5
3
4
2
4
1
2
4
3
...

result:

ok 1000 numbers

Test #31:

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

input:

100 130 1000
90 21
67 17
23 29
60 59
58 31
85 7
65 85
6 62
98 63
37 2
8 98
24 44
52 28
49 64
21 58
66 60
32 28
73 65
53 17
97 60
76 89
95 78
60 41
95 77
48 58
72 33
85 54
71 20
57 86
16 58
51 58
24 61
17 56
13 2
97 54
61 18
28 14
72 34
66 93
21 44
100 86
29 24
80 67
76 80
53 87
66 4
100 87
79 26
44 ...

output:

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

result:

ok 1000 numbers

Test #32:

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

input:

100 151 1000
13 29
25 59
82 88
71 73
29 91
48 39
73 20
26 45
45 9
98 8
38 3
13 96
12 2
74 18
89 59
50 22
38 90
63 55
41 36
70 98
87 94
86 27
40 21
66 92
90 32
10 3
62 73
19 40
71 87
94 33
57 61
25 49
43 78
30 26
89 80
35 49
72 58
76 49
44 98
84 2
92 82
91 97
10 25
36 16
47 72
78 47
42 6
87 72
47 82
...

output:

3
6
3
4
4
2
3
2
4
3
6
5
5
4
3
6
5
5
4
1
5
5
2
5
4
5
6
4
6
8
4
3
5
6
3
7
4
5
4
5
4
6
2
0
5
4
5
7
5
5
2
5
7
3
5
5
4
7
7
4
5
5
6
2
4
5
4
6
3
5
1
4
4
5
4
4
3
5
2
6
5
4
6
3
6
7
4
5
6
5
3
6
5
3
4
4
2
6
7
6
6
2
6
2
5
3
6
5
1
5
5
3
3
8
4
4
4
5
4
7
6
3
3
4
3
4
5
4
4
6
2
3
4
7
6
5
4
3
4
6
6
5
4
5
3
6
5
5
5
5
...

result:

ok 1000 numbers

Test #33:

score: -100
Runtime Error

input:

1000 1015 50000
6 721
586 869
596 598
400 723
147 491
711 8
990 473
318 688
493 260
742 800
274 252
405 133
526 270
577 343
694 596
100 750
762 946
963 499
888 828
491 417
850 911
161 745
20 293
507 118
415 700
981 66
985 583
726 63
739 907
24 831
626 747
499 357
534 901
2 682
581 931
4 985
489 667
...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-02-08 23:00:47 | OpenSource Project