P3393 Escape from Zombie Island

The country where Xiao A lives has been invaded by zombies! Xiao A plans to escape the country via the only international airport. The country has $N$ cities connected by roads. There are $M$ bidirectional roads. There are no self-loops or multiple edges. Among them, $K$ cities have already been taken over by zombies. Entering any such city will result in infection, so these cities cannot be entered. Any city that can be reached from any zombie-controlled city by traversing at most $S$ roads is considered dangerous. In other words, if a city’s distance to any zombie-controlled city is at most $S$, then it is dangerous. Xiao A lives in city $1$, the international airport is in city $N$, and these two cities are not invaded. Xiao A spends an entire day to traverse each single road (moving directly from one city to another), so he must stay at an inn at night. Inns in safe cities are cheaper and cost $P$, while inns in dangerous cities need extra security measures and thus cost $Q$. All dangerous cities share the same lodging price, and so do all safe cities. In cities $1$ and $N$, no lodging is required. Xiao A is frugal, so he wants to know the minimum cost to travel from city $1$ to city $N$. The input guarantees that there exists a path and that he can successfully escape.

- The first line contains $4$ integers $N, M, K, S$. - The second line contains two integers $P, Q$. - The next $K$ lines each contain one integer $c_i$, the index of a zombie-controlled city. - The next $M$ lines each contain two integers $a_i, b_i$, indicating an undirected edge.

Output a single integer, the minimum total cost.

 - For $20\%$ of the testdata, $N \le 50$. - For $100\%$ of the testdata, $2 \le N \le 10^5$, $1 \le M \le 2 \times 10^5$, $0 \le K \le N - 2$, $0 \le S \le 10^5$, $1 \le P < Q \le 10^5$. Translated by ChatGPT 5