Woburn Challenge 2017-18 Round 4 - Senior Division
Problem 2: Strange Travels
Desperate to find more allies to join in the fight against Thanos, the Avengers have requested assistance from Doctor Strange, a powerful magician. Strange is willing to help, but he'll need some assistance of his own first. To fully apply his powers to the fight, he'll need to gather together a set of artifacts from hidden sanctums around the world!
There are N (2 ≤ N ≤ 100,000) sanctums, numbered from 1 to N, spread out all across the Earth. It would take far too long to travel amongst them by conventional means, but Doctor Strange has access to a convenient alternative – magical portals. There are M (0 ≤ M ≤ 200,000) one-way portals, with the i-th of them allowing for instantaneous travel from sanctum Ai to Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi). No two portals connect the same pair of sanctums in the same direction.
There are K (1 ≤ K ≤ N − 1) artifacts which Strange requires, with the i-th of them being held in sanctum Si (2 ≤ Si ≤ N). No artifact is in sanctum 1, and no two artifacts are located in the same sanctum.
Doctor Strange is initially located in sanctum 1, also known as the Sanctum Sanctorum. He'll need to recover all K artifacts back to the Sanctum Sanctorum, one by one. In particular, for each artifact i in order, he'll need to warp through a sequence of 1 or more portals to reach sanctum Si, collect the artifact, and then warp through a sequence of 1 or more portals to return to sanctum 1 before heading back out for the next one. Note that he may not carry multiple artifacts at a time, and must collect the K artifacts in order. Overall, he'll be required to visit the following sequence of sanctums:
1 → S1 → 1 → S2 → 1 → … → 1 → SK → 1
Determine the minimum number of portal warps which Doctor Strange will need to perform to achieve his goal. Unfortunately, it may instead turn out to be impossible to visit the entire required sequence of sanctums, in which case you should output −1 instead.
In test cases worth 6/20 of the points, N ≤ 100 and M ≤ 2000.
In test cases worth another 6/20 of the points, N ≤ 2000 and M ≤ 2000.
The first line of input consists of two space-separated integers, N and M.
M lines follow, the i-th of which consists of two space-separated integers, Ai and Bi, for i = 1..M.
The next line consists of a single integer K.
K lines follow, the i-th of which consists of a single integer, Si, for i = 1..K.
Output a single integer, either the minimum number of warps required to recover all of the artifacts, or −1 if not all of them can be recovered.
Sample Input 1
4 6 1 2 2 3 3 1 1 3 4 3 3 4 2 4 2
Sample Output 1
Sample Input 2
4 5 1 2 3 1 1 3 4 3 3 4 2 4 2
Sample Output 2
In the first case, Doctor Strange can warp through the following sequence of sanctums:
1 → 3 → 4 → 3 → 1 → 2 → 3 → 1
In the second case, Doctor Strange would be able to recover the first artifact and then reach the second one, but he would then be unable to return to sanctum 1 with it.
Point Value: 12 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Apr 20, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3