FLIPKART Coding Question – Solved

Undirected Coloured Graph Shortest Path You are given an undirected weighted graph G(V, E) where each vertex is assigned a colour. Vertices form pairs of the same colour. Thus, total pairs = V/2 (if V is even) or (V/2)+1 (if V is odd). Each pair is assigned a unique colour. A query Q specifies a colour, and your task is to find the shortest path (in terms of weight) between the two vertices sharing this colour. Input Format: - The first line contains two integers V and E separated by a space (number of vertices and edges). - The next E lines each contain three integers u, v, and w: an edge between vertex u and vertex v with weight w. - The next V/2 (or V/2+1 if V is odd) lines specify the vertex pairs for each colour (each line has two vertex indices). If V is odd, the last line contains a single vertex with no pair. - The final line contains a single integer Q, representing the colour number to query. Output Format: - Print the shortest path (by weight) between the vertex pair corresponding to colour Q. - Each vertex in the path should be printed in order, separated by a single space. Constraints: - 2 ≤ V ≤ 100 - 1 ≤ E ≤ 100 Sample Input 1: 7 8 0 6 10 0 2 11 2 4 9 6 4 2 5 2 7 5 1 8 1 4 4 3 4 3 0 1 2 3 5 6 4 3 Sample Output 1: 5 1 4 6 Explanation: There are 7 vertices and 8 edges. Colour 1 → nodes 0, 1 Colour 2 → nodes 2, 3 Colour 3 → nodes 5, 6 Colour 4 → node 4 (no pair) Query = 3 → Find shortest path between 5 and 6. Shortest weighted path: 5 → 1 → 4 → 6