hey,this is tharun…
You have an undirected graph G with N nodes and M edges. There are K mail carriers, each located at a specific node and able to deliver mail to nodes within a certain distance.
Each mail carrier is initially at a specific node Xi and can deliver mail to any node that is at most Di distance away from Xi. The distance between two nodes is defined as the total number of nodes on the shortest path between them.
The task is to determine whether it is possible for the mail carriers to deliver mail to all nodes in the graph.
You need to write a program that takes the number of test cases T as input. Each test case consists of the following:
- N, M, K: the number of nodes, the number of edges, and the number of mail carriers.
- K integers representing the indices of the nodes where the mail carriers are located.
- K integers representing the maximum distance each mail carrier can travel.
- M lines containing two integers each, representing the edges between nodes.
For each test case, the program should output “YES” if the mail can be delivered to every node, and “NO” otherwise.
For example, consider the following input:
3 3 2
3 3 1
This means there are two test cases. In the first test case, there are 3 nodes, 3 edges, and 2 mail carriers. Mail carrier 1 is located at node 1 and can travel a distance of 1. Mail carrier 2 is located at node 3 and can also travel a distance of 1. The edges in this case are (1, 2), (1, 3), and (2, 3).
The program should output “YES” for the first test case because both mail carriers can reach all nodes within their allowed distance.
In the second test case, there are 3 nodes, 3 edges, and 1 mail carrier. The mail carrier is located at node 1 and can travel a distance of 1. The edges are (1, 2) and (1, 3).
The program should output “NO” for the second test case because the mail carrier at node 1 cannot reach node 3 within the allowed distance.
I hope this explanation helps you understand the problem better. Let me know if you have any further questions!
please checkout my solution
Would you pls checkout my submission wherein I have used BFS.
I am getting WA in 2 test cases. Can you pls tell where is my code going wrong