FLIPKART Coding Question – Solved

Question

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

TreasuresBase Expert · Accepted Answer

#include using namespace std; int n, m; unordered_map>> h; unordered_map> colours; vector solve(int start, int end) { vector distance(n + 1, INT_MAX); vector parent(n + 1, -1); deque> q; distance[start] = 0; q.push_back(make_pair(start, 0)); while (!q.empty()) { pair front = q.front(); int node = front.first; int dist = front.second; q.pop_front(); for (size_t i = 0; i < h[node].size(); ++i) { int neighbor = h[node][i].first; int weight = h[node][i].second; if (distance[neighbor] > dist + weight) { distance[neighbor] = dist + weight; parent[neighbor] = node; q.push_back(make_pair(neighbor, dist + weight)); } } } vector path; int curr = end; while (curr != -1) { path.push_back(curr); curr = parent[curr]; } reverse(path.begin(), path.end()); return path; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; h[a].push_back(make_pair(b, c)); h[b].push_back(make_pair(a, c)); } for (int i = 1; i <= (n >> 1); ++i) { int u, v; cin >> u >> v; colours[i] = make_pair(u, v); } if (n % 2) { int dummy; cin >> dummy; } int key; cin >> key; int start = colours[key].first; int end = colours[key].second; vector result = solve(start, end); for (int x : result) { cout << x << " "; } cout << " "; return 0; }

FLIPKART Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions