Given a unweighted, undirected graph of N vertices and M edges, vertices are numbered from 1 to N. Also there are K special vertices. You have to answer Q queries. In each query, you're given a vertex V. You have to print shortest distance of nearest special vertex. If there is no special vertex reachable from V, print -1.
Note : Graph doesn't contain multiple edges or self loops and it may be disconnected.
Constraints :
1 <= N, K, Q <= 1e5
1 <= M <= 2e6
Sample Input:
5 3 3 // N M K
1 2 // edge 1
2 3 // edge 2
1 3 // edge 3
1 3 5 // special vertices
5 // Q
1 // V for 1st query
2 // " " " 2nd " "
3 // " " " 3rd " "
4 // " " " 4th " "
5 // " " " 5th " "
Sample Output:
0
1
0
-1
0
P.S. : This problem was asked in Codechef's CCDSAP advanced contest on 22th Sept.,2019. Now it's over.
You can use BFS.
But at first add all the special nodes to queue and set the distances of special nodes 0 and then run the BFS. And calculate the distance of each node in that way.
Then you can answer each query in O(1).
Sorry for my bad English.
wont that time out given K, M, N are order of 1e5 ?
No. The idea is to perform a multisource BFS. You first place all the special vertices in a queue and afterwards you run a normal BFS. Then, you will have a dist array with the shortest path from a given node to the nearest special node. Since you only run BFS once, the complexity will be O(V + E). All queries will be answered in O(1)
Dude, that was private contest and It was clearly mentioned not to discuss problem on public platforms, even after contest. Don't disrespect their policy.