Shortest Path Queries in a Weighted Graph - Juspay Hiring Challenge 2026

Problem Preview

"You are given an undirected weighted graph with N vertices (numbered from 1 to N) and M edges. Your task is to process Q queries of two different types. ### Query Types #### Type 1 `1 u v 0` Find the length of the shortest path between vertices u and v, and add this distance to a running total. #### Type 2 `2 u v w` An edge already exists between vertices u and v. Update the weight of this edge to w. After processing all queries, output the final value of the running total. ### Input Format The first line contains an integer T, the number of test cases. For each test case: - The first line contains three integers N, M, and Q — the number of vertices, edges, and queries. - The next M lines each contain three integers u, v, and w, representing an undirected edge between u and v with weight w. - The next Q lines describe the queries in one of the following formats: - `1 u v 0` - `2 u v w` ### Output Format For each test case, print a single integer — the sum of the shortest path distances obtained from all Type 1 queries. Explanation: Initially, the shortest distance from 1 to 4 is 3 + 4 + 2 = 9. After updating the weight of edge (1, 4) to 5, the shortest distance from 1 to 4 becomes 5. Finally, the shortest distance from 2 to 4 is 4 + 2 = 6. The required sum is: 9 + 5 + 6 = 20 Note: The sample output should be 20, not 18. The provided sample output appears to be incorrect."