DMOPC '18 Contest 2 P3 - Thanksgiving Feast

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Java 5.0s
Memory limit: 256M
Java 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, \ldots, 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 a five space-separated integers N, M, K, A, B.
The next line will contain K space-separated integers s_1, s_2, \ldots, 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



There are no comments at the moment.