C++ Solution using Dijkstra's Algorithm


#1
#define pii pair<int,int>

int dijkstras(int src, int dest, int n, vector<vector<pii>> &adj){
    vector<int> dist(n+1, INT_MAX);
    vector<bool> vis(n+1, false);
    dist[src]=0;
    priority_queue<pii, vector<pii>, greater<pii>> minHp;
    minHp.push({0,src});
    
    while(!minHp.empty()){
        pii p=minHp.top();
        int u=p.second;
        minHp.pop();
        if(vis[u]) continue;
        vis[u]=true;
        
        for(auto child:adj[u]){
            int v=child.first;
            int w=child.second;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                minHp.push({dist[v], v});
            }
        }
    }
    return dist[dest];
}

int Solution::solve(int A, vector<vector<int> > &B, int C, int D, vector<vector<int> > &E) {
    vector<vector<pii>> adj(A+1);
    for(auto v:B){
        adj[v[0]].push_back({v[1], v[2]});
    }
    
    int ans=INT_MAX;
    // take one edge at a time from E
    for(auto v:E){
        if(v[0]>A || v[1]>A) continue;
        
        adj[v[0]].push_back({v[1], v[2]});
        adj[v[1]].push_back({v[0], v[2]});
        int temp=dijkstras(C,D,A,adj);
        ans=min(ans, temp);
        adj[v[0]].pop_back();
        adj[v[1]].pop_back();
        
    }
    return (ans==INT_MAX) ? -1 : ans;
}


#2

why by popping our ans is getting submitted else partially?
***WHY IS IT SO?***
adj[v[0]].pop_back();
adj[v[1]].pop_back();


#3

Because we are only allowed to take one edge from E, so after running djikstra with a particular edge, we will have to remove it as we don’t want multiple edges from E be in our minimal path. Hope it makes sense :slight_smile:


#4

What is the time complexity of this solution??