The Memory Palace Corridors
Loading content...
Input Format
Loading content...
Output Format
Loading content...
Examples
Example 1
Example 2
Constraints
•
2 ≤ n ≤ 1000
•
1 ≤ m ≤ 10000
•
0 ≤ d < n-1
•
Rooms 1 and n are never distractions
Code
A detective uses a "memory palace" technique where memories are stored in rooms connected by corridors. The palace is represented as an undirected graph with n rooms (numbered 1 to n) and m corridors.
The detective starts in room 1 and needs to reach room n. However, some rooms contain distractions that must be avoided.
Determine the minimum number of corridors the detective must traverse to reach room n from room 1 while avoiding all distraction rooms. If it's impossible, return -1.
Room 1 and room n are guaranteed to NOT be distraction rooms.
The first line contains three integers n, m, and d (rooms, corridors, distractions). The next m lines each contain two integers u and v representing a corridor between rooms u and v. The last line contains d space-separated integers representing the distraction room numbers.
Print the minimum number of corridors to traverse, or -1 if impossible.