Minimum Weighted Subgraph With the Required Paths LeetCode solution in C++

1
typedef long long ll;
2

3
class Solution {
4
 private:
5
  const ll kInf = 1e18;
6
  vector<ll> Dijkstra(vector<vector<pair<int, ll>>> &adj, int src) {
7
    int n = adj.size();
8
    vector<ll> dist(n, kInf);
9
    dist[src] = 0;
10
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
11
    // pq contains pairs of <the current distance estimate from src to id, id>
12
    pq.push(make_pair(0, src));
13
    while (!pq.empty()) {
14
      auto [d, cur] = pq.top();
15
      pq.pop();
16
      if (d != dist[cur]) continue;
17
      for (auto [nei, w] : adj[cur]) {
18
        if (dist[nei] > d + w) {
19
          dist[nei] = d + w;
20
          pq.push(make_pair(dist[nei], nei));
21
        }
22
      }
23
    }
24
    return dist;
25
  }
26

27
 public:
28
  long long minimumWeight(int n, vector<vector<int>> &edges, int src1, int src2, int dest) {
29
    // build the graphs
30
    vector<vector<pair<int, ll>>> adj(n);
31
    vector<vector<pair<int, ll>>> rev(n); // the graph with reversed edges
32
    int u, v, w;
33
    for (auto &e : edges) {
34
      u = e[0], v = e[1], w = e[2];
35
      adj[u].push_back(make_pair(v, w));
36
      rev[v].push_back(make_pair(u, w));
37
    }
38
    // Dijkstra
39
    vector<ll> dist_from_src1 = Dijkstra(adj, src1);
40
    vector<ll> dist_from_src2 = Dijkstra(adj, src2);
41
    vector<ll> dist_to_dest = Dijkstra(rev, dest);
42
    // find the smallest w[i]
43
    ll ans = kInf;
44
    for (int i = 0; i < n; i++) {
45
      ans = min(ans, dist_from_src1[i] + dist_from_src2[i] + dist_to_dest[i]);
46
    }
47
    return ans == kInf ? -1 : ans;
48
  }
49
};