Maximum Path Quality of a Graph LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maximalPathQuality(vector<int> &values, vector<vector<int>> &edges, int maxTime) {
4
    int n = values.size();
5
    int res = values[0];
6
    vector<vector<pair<int, int>>> graph(n);
7
    for (int i = 0; i < edges.size(); i++) {
8
      graph[edges[i][0]].push_back({edges[i][1], edges[i][2]});
9
      graph[edges[i][1]].push_back({edges[i][0], edges[i][2]});
10
    }
11

12
    vector<int> visited(n, 0);
13
    dfs(graph, values, visited, res, 0, 0, 0, maxTime);
14
    return res;
15
  }
16

17
  void dfs(vector<vector<pair<int, int>>> &graph, vector<int> &values, vector<int> &visited,
18
           int &res, int node, int score, int time, int &maxTime) {
19
    if (time > maxTime) return;
20

21
    if (visited[node] == 0) score += values[node];
22

23
    &nbsp;
24
    &nbsp;
25
    &nbsp;
26
    &nbsp;
27
    visited[node]++;
28

29
    &nbsp;
30
    &nbsp;
31
    &nbsp;
32
    &nbsp;
33
    &nbsp;
34
    &nbsp;
35
    &nbsp;
36
    if (node == 0) res = max(res, score);
37

38
    for (auto it : graph[node]) {
39
      int neigh = it.first;
40
      int newTime = time + it.second;
41
      dfs(graph, values, visited, res, neigh, score, newTime, maxTime);
42
    }
43

44
    visited[node]--;
45
  }
46
};