Minimum time

Moderate

0/80

Average time to solve is 15m

15 upvotes

Asked in companies

Problem statement

You are given an arbitrary graph consisting of V vertices and E edges, a source node (S) and a destination node (D). Every node of the graph has a colour (Red, Blue or Green) associated with it. The cost of travelling from one node to some adjacent node takes 1 second. If you stop at a node for 1 second, you will get a colour ball of the colour of the current node.

You have to find the minimum time taken in order to reach from source to destination node ensuring that the number of balls of each colour is equal and non-zero. The source and destination nodes will always be in different colours.

Note:

1. The given graph is never empty and consists of at least 3 nodes with the colour Red, Green and Blue each.
2. There are no self-loops(an edge connecting a node to itself) in a graph.
3. There are no parallel edges i.e no two nodes are directly connected by more than 1 edge in the given graph.
4. The nodes in the graph are numbered from 1 to V.
5. All the edges in the graph are bidirectional.
6. You can stay at one node for more than 1 second as well, but every second you stay there you will get an additional colour ball of the colour of that node.
7. Number of edges(E) in the graph is always equal to V-1.
8. You can also collect the ball from the destination and the source node itself. Also if you reach the destination without having an equal number of balls for each colour, the time calculated would not be valid.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer T, the number of test cases.

The first line of each test case contains two space-separated integers V, and E denoting the number of vertices and number of edges in the given graph respectively.

The second line of each test case denotes V space-separated integers  (0 / 1/ 2) denoting the colour of vertex i, where 1 <= i <= V and 0 denotes “Red” colour, 1 denotes “Blue” colour and 2 denotes “Green” colour.

From the third line onwards of each test case, the next 'E' lines will denote the edges of the given graph.

Every edge is defined by two single space-separated integers 'a' and 'b', which signifies an edge between node ‘a’ and node 'b'.

The last line of each test case consists of two space-separated integers S and D, denoting the source node and destination node.

Output Format:

Return an integer denoting the minimum time to reach from source node (S) to destination node (D), fulfilling mentioned conditions.

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
3 <= V <= 5000
E = V - 1
1 <= a,b <= V

Time Limit: 1 sec

Sample Input 1:

2
6 5
1 0 2 1 2 0
1 2
1 3    
3 4
3 5
2 6
6 5   
5 4
0 0 1 2 1
1 2
2 3
3 4
3 5 
1 5

Sample Output 1:

7
8

Explanation for Sample Input 1:

For the first test case of sample input 2, Source Node, S = 6 and Destination Node, D = 5.
The tree depicted is as follows:

For the second test case of sample input 2, Source Node, S = 1 and Destination Node, D = 5.
The tree depicted is as follows:

Sample Input 2:

Sample Output 2:

5
6

Console