Minimum Weighted Subgraph With the Required Paths LeetCode solution in Java

1
class Solution {
2
  ArrayList<int[]>[] nextGraph, preGraph;
3

4
  public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
5
    buildGraph(n, edges);
6

7
    long[] src1To = new long[n], src2To = new long[n], toDest = new long[n];
8
    Arrays.fill(src1To, -1);
9
    Arrays.fill(src2To, -1);
10
    Arrays.fill(toDest, -1);
11

12
    shortestPath(src1, src1To, nextGraph);
13
    shortestPath(src2, src2To, nextGraph);
14
    shortestPath(dest, toDest, preGraph);
15

16
    long res = -1;
17
    for (int i = 0; i < n; i++) {
18
      long d1 = src1To[i], d2 = src2To[i], d3 = toDest[i];
19
      if (d1 >= 0 && d2 >= 0 && d3 >= 0) {
20
        long d = d1 + d2 + d3;
21
        if (res == -1 || d < res) {
22
          res = d;
23
        }
24
      }
25
    }
26

27
    return res;
28
  }
29

30
  private void buildGraph(int n, int[][] edges) {
31
    nextGraph = new ArrayList[n];
32
    preGraph = new ArrayList[n];
33
    for (int i = 0; i < n; i++) {
34
      nextGraph[i] = new ArrayList<int[]>();
35
      preGraph[i] = new ArrayList<int[]>();
36
    }
37

38
    for (int[] edge : edges) {
39
      int from = edge[0], to = edge[1], weight = edge[2];
40
      nextGraph[from].add(new int[] {to, weight});
41
      preGraph[to].add(new int[] {from, weight});
42
    }
43
  }
44

45
  private void shortestPath(int src, long[] srcTo, ArrayList<int[]>[] graph) {
46
    PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
47
    heap.offer(new long[] {src, 0});
48

49
    while (!heap.isEmpty()) {
50
      long[] node = heap.poll();
51
      int to = (int) node[0];
52
      long dist = node[1];
53
      if (srcTo[to] != -1 && srcTo[to] <= dist) continue;
54
      srcTo[to] = dist;
55
      for (int[] next : graph[to]) {
56
        heap.offer(new long[] {next[0], dist + next[1]});
57
      }
58
    }
59
  }
60
}