Useful Extra Edges

// Prob: https://www.interviewbit.com/problems/useful-extra-edges/

#define pii pair<int, int>
#define pb push_back
#define F first
#define S second

int dijkstras(int n, int src, int dst, vector<vector<pii>> &g) {
    vector<int> d(n + 1, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    vector<bool> vis(n + 1, false);

    d[src] = 0;
    q.push({0, src});

    while(!q.empty()) {
        int mn = q.top().F;
        int v = q.top().S;
        q.pop();

        if(vis[v]) continue;
        vis[v] = true;

        for(auto child: g[v]) {
            if(d[child.F] > mn + child.S) {
                d[child.F] = mn + child.S;
                q.push({d[child.F], child.F});
            }
        }
    }

    return d[dst];
}

int Solution::solve(int A, vector<vector<int> > &B, int C, int D, vector<vector<int> > &E) {
    vector<vector<pii>> g(A + 1);
    for(int i = 0; i < B.size(); i++) {
        g[B[i][0]].pb({B[i][1], B[i][2]});
    }

    int res = INT_MAX;

    for(auto x: E) {
        if(x[0] > A or x[1] > A) continue;
        g[x[0]].pb({x[1], x[2]});
        g[x[1]].pb({x[0], x[2]});

        int tmp = dijkstras(A, C, D, g);
        res = min(res, tmp);

        g[x[0]].pop_back();
        g[x[1]].pop_back();
    }

    if(res == INT_MAX) res = -1;
    return res;
}