DMOPC '18 Contest 2 P3 - Thanksgiving Feast

Points: 10 (partial)

Time limit: 1.0s

Java 2.5s

Memory limit: 256M

Author:

Problem type

Mimi is attending a Thanksgiving feast! She lives in a town with $N$ $N$ buildings numbered from $1$ $1$ to $N$ $N$ and $M$ $M$ unweighted bidirectional roads connecting them. The $i^\text{th}$ $i^{th}$ road connects buildings $a_i$ $a_{i}$ and $b_i$ $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$ $K$ buildings $s_1, s_2, \dots, s_K$ $s_{1}, s_{2}, \dots, s_{K}$ which sell gifts. Mimi is currently at building $A$ $A$ and the feast is at building $B$ $B$ . She needs to visit at least one of the $K$ $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$ $B$ before buying a gift.

Constraints

$1 \le A, B, a_i, b_i, s_j \le N$ $1 \leq A, B, a_{i}, b_{i}, s_{j} \leq N$
$1 \le K \le N$ $1 \leq K \leq N$
$1 \le M \le \binom N 2$ $1 \leq M \leq (\binom{N}{2})$

Subtask 1 [30%]

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

Subtask 2 [30%]

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

Subtask 3 [40%]

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

Input Specification

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

Output Specification

Output a single integer, the shortest distance.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample 1

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

Sample Input 2

Copy

Sample Output 2

Copy

Comments

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.