Another Random Contest 1 P6 - Smash Bros

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Andy just started the story mode for Super Smash Bros – World of Light. World of Light consists of N nodes and M edges connecting the N nodes. Unknown Hand is at location Y, and Andy starts at location X.

Each node is guarded by a corrupted character (including position X) and takes a certain amount of time to defeat. After the corrupted character is defeated, you can go through the node and adjacent edges as many times as you want without any cost in time. Andy's favourite character, Mr. Game & Watch, is located at location A, and he would like to obtain Mr. Game & Watch in order to defeat the Unknown Hand.

Andy obtains Mr. Game & Watch if he reaches node A. However, he can't tell where node A is, so he asks you to answer Q queries to determine the minimum amount of time he needs to beat the game if a location given is location A.


For all subtasks:

1 \le X, Y, u_i, v_i \le N \le 10^5

1 \le M, Q \le 2 \times 10^5

1 \le a_i \le 10^9

The graph is guaranteed to be connected.

Subtask 1 [10%]

Q = 1

A = X

Subtask 2 [40%]

1 \le N \le 1\,000

1 \le M, Q \le 2\,000

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains five integers N, M, X, Y, and Q.

The next line contains an array a of N integers with the ith integer representing the time it takes to beat the corrupted character at node i.

Each of the following M lines contains two integers u_i and v_i. Each represents a bidirectional edge connecting u_i and v_i.

The last Q lines contain one integer A, asking for the minimum time to go from node X to node Y while passing by node A.

Output Specification

For each of the Q queries, output each answer on one line.

Sample Input

7 8 1 7 7
2 3 7 6 4 3 5
1 2
2 5
4 5
5 3
5 6
3 6
6 7
5 7

Sample Output


Sample Explanation

When A is 1, go from 1 \to 2 \to 5 \to 7, which costs 2+3+4+5 = 14.

When A is 4, go from 1 \to 2 \to 5 \to 4 \to 5 \to 7, which requires Andy to defeat the enemies at 1, 2, 4, 5, 7, for a total cost of 2+3+6+4+5 = 20.


There are no comments at the moment.