Round 1: Problem Solving Round I was asked a graph problem based on shortest path with constraints. Problem: You are given an undirected graph with n nodes and m weighted edges. Additionally, there are k special edges (magical bridges) that have zero cost and can be used at most once each. You need to find the minimum time required to travel from node 1 to node n using at most k such edges. If it is not possible, return -1. Example: n = 4, m = 4, k = 1 edges = [[1,2,10],[2,4,10],[1,3,5],[3,4,20]] bridges = [[1,4]] Output: 0 Approach: This problem is a variation of Dijkstra’s algorithm with an additional state. We define a state as (node, k_used), where k_used is the number of free edges used so far. We maintain: dist[node][k_used] = minimum cost to reach node using k_used bridges From each node: - Traverse normal edges → cost increases - Use magical bridge → cost remains same, but k_used increases Finally: Answer = min(dist[n][i]) for i in [0, k] # Code ```cpp [] class Solution { public: int shortestPathWithKFreeEdges(int n, vector>& edges, vector>& bridges, int k) { vector>> adj(n+1); vector> freeEdges(n+1); for(auto &e : edges) { adj[e[0]].push_back({e[1], e[2]}); adj[e[1]].push_back({e[0], e[2]}); } for(auto &b : bridges) { freeEdges[b[0]].push_back(b[1]); freeEdges[b[1]].push_back(b[0]); } vector> dist(n+1, vector(k+1, LLONG_MAX)); priority_queue, vector>, greater<>> pq; dist[1][0] = 0; pq.push({0,1,0}); while(!pq.empty()) { auto [d,u,used] = pq.top(); pq.pop(); if(d > dist[u][used]) continue; for(auto &it : adj[u]) { int v = it.first, w = it.second; if(dist[v][used] > d + w) { dist[v][used] = d + w; pq.push({dist[v][used], v, used}); } } if(used < k) { for(auto &v : freeEdges[u]) { if(dist[v][used+1] > d) { dist[v][used+1] = d; pq.push({d, v, used+1}); } } } } long long ans = LLONG_MAX; for(int i = 0; i <= k; i++) { ans = min(ans, dist[n][i]); } return ans == LLONG_MAX ? -1 : ans; } }; ``` Verdict: Medium/Hard level problem. Requires understanding of Dijkstra with state expansion.