DMOPC '18 Contest 2 P3 - Thanksgiving Feast

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 2.5s
Memory limit: 256M

Problem type

Mimi is attending a Thanksgiving feast! She lives in a town with N buildings numbered from 1 to N and M unweighted bidirectional roads connecting them. The i^\text{th} road connects buildings a_i and b_i. Mimi is a good guest, so she wants to bring a gift for the host. However, Mimi is also a procrastinator! The Thanksgiving feast is soon and she hasn't bought a gift yet. There are K buildings s_1, s_2, \dots, s_K which sell gifts. Mimi is currently at building A and the feast is at building B. She needs to visit at least one of the K buildings and go to the feast. Help her find the length of the shortest way to do so!

It is guaranteed that there exists a way. Mimi is allowed to pass through B before buying a gift.


1 \le A, B, a_i, b_i, s_j \le N
1 \le K \le N
1 \le M \le \binom N 2

Subtask 1 [30%]

1 \le K \le 1\,000
1 \le N \le 1\,000
1 \le M \le 2\,000

Subtask 2 [30%]

1 \le K \le 10
1 \le N \le 100\,000
1 \le M \le 200\,000

Subtask 3 [40%]

1 \le K \le 100\,000
1 \le N \le 100\,000
1 \le M \le 200\,000

Input Specification

The first line of input will contain five space-separated integers N, M, K, A, B.
The next line will contain K space-separated integers s_1, s_2, \dots, s_K representing the buildings which sell gifts.
The next M lines each contain two space-separated integers, a_i and b_i.

Output Specification

Output a single integer, the shortest distance.

Sample Input 1

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

Sample Output 1


Explanation for Sample 1

Mimi starts at building 1. She passes by B=2, to head to 3. She then returns to 2, giving a total length of 3.

Sample Input 2

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

Sample Output 2



  • 0
    lightning2  commented on April 25, 2020, 3:15 a.m.

    Does anyone mind taking a look at my code? I have WAs from each batch but I can't think of any case that would break my code. What I did was do BFS from the start and end points simultaneously until I reach the first store that both sides have already reached, in which case, I exit the program. Thanks in advance!

    • 2
      sushi  commented on April 25, 2020, 12:57 p.m.

      I dont think you should to the bfs simultaneously, rather you should do it separately.

      • 0
        lightning2  commented on April 25, 2020, 5:54 p.m.

        Thank you for the feedback! But quick question, why is it faulty to do BFS from both sides simultaneously? I changed my code as you suggested and it passed.