Reach Quickly

5

5 votes
Algorithms, Breadth-first search, Graphs
Problem

You are given a connected graph consisting of N vertices and M bidirectional edges. You are also given an array A of length X and an array B of length Y.

The time to reach a vertex V from an array of vertices S is defined as the minimum of the shortest distance between U and V for all U in S.

The cost of an array of vertices S is defined as the sum of the time to reach vertex V from S for all V in B.

Find the last index of the smallest prefix of A having the minimum cost.

Input Format:

  • The first line of input contains a single integer T, denoting the number of test cases.
  • The first line of each test case contains two integers N and M, denoting the number of vertices and the number of initial edges respectively.
  • The following M lines contain 2 integers u and v, denoting a bidirectional edge between vertex u and vertex v.
  • The next line contains X and Y, denoting the length of the arrays A and B respectively.
  • The next line contains X integers, denoting the elements of array A.
  • The last line contains Y integers, denoting the elements of array B.

Output Format:

For each test case, print the last index of the smallest prefix of A having the minimum cost.

Constraints:

1<=T<=10

1<=N<=105

N1<=M<=105

0<=u,v<N

1<=X,Y<=N

0<=A[i],B[i]<N

Sample Input
3
6 5
0 1
1 2
2 4
4 3
4 5
3 3
4 2 1
0 5 2
3 3
0 1
1 2
2 0
2 1
1 2
0
4 3
0 1
1 2
1 3
3 1
0 1 2
3
Sample Output
2
0
1
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

First test case:-
The cost of [4] is dist(4,0)+dist(4,5)+dist(4,2)=3+1+1=5.
The cost of [4,2] is min(dist(4,0),dist(2,0))+min(dist(4,5),dist(2,5))+min(dist(4,2),dist(2,2))=2+1+0=3.
Similarly, the cost of [4,2,1] is 1+1+0=2.
Therefore the minimum cost is 2 and the last index of the smallest prefix of A having the minimum cost is 2.
Hence, the answer is 2.

Second test case:-
The cost of [1] is 1.
The cost of [1,2] is also 1.
Therefore the minimum cost is 1 and the last index of the smallest prefix of A having the minimum cost is 0.
Hence, the answer is 0.

Third test case:-
Since, B consists of only one vertex 3, the cost of an array of vertices is just the time to reach 3 from the array of vertices.
The cost of [0] is 2.
The cost of [0,1] is 1.
The cost of [0,1,2] is 1.
Therefore the smallest prefix of A having the minimum cost ends at index 1.
Hence, the answer is 1.

Editor Image

?