Zorvyn OA | Shortest Path with K Free Edges (Dijkstra + State)

Role: SDE Intern
Company: Zorvyn
Experience: Fresher

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

class Solution {
public:
    int shortestPathWithKFreeEdges(int n, vector>& edges, vector>& bridges, int k) {
    vector<vector<pair<int,int>>> adj(n+1);
    vector<vector<int>> 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<vector<long long>> dist(n+1, vector<long long>(k+1, LLONG_MAX));

    priority_queue<tuple<long long,int,int>, vector<tuple<long long,int,int>>, 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.