Maximum Path Quality of a Graph LeetCode solution in Java

1
class Solution {
2
  public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
3
    int n = values.length;
4
    List<int[]>[] adj = new List[n];
5
    for (int i = 0; i < n; ++i) adj[i] = new LinkedList();
6
    for (int[] e : edges) {
7
      int i = e[0], j = e[1], t = e[2];
8
      adj[i].add(new int[] {j, t});
9
      adj[j].add(new int[] {i, t});
10
    }
11
    int[] res = new int[1];
12
    int[] seen = new int[n];
13
    seen[0]++;
14
    dfs(adj, 0, values, maxTime, seen, res, values[0]);
15
    return res[0];
16
  }
17

18
  private void dfs(
19
      List<int[]>[] adj, int src, int[] values, int maxTime, int[] seen, int[] res, int sum) {
20
    if (0 == src) {
21
      res[0] = Math.max(res[0], sum);
22
    }
23
    if (0 > maxTime) return;
24
    for (int[] data : adj[src]) {
25
      int dst = data[0], t = data[1];
26
      if (0 > maxTime - t) continue;
27
      seen[dst]++;
28
      dfs(adj, dst, values, maxTime - t, seen, res, sum + (1 == seen[dst] ? values[dst] : 0));
29
      seen[dst]--;
30
    }
31
  }
32
}