leetcode

0 class Solution {

1 vector<vector<int>> adj;

2 vector<bool> visited;

3 vector<int> distance, parent;

4

5 void distance_parent(int start) {

6 stack<pair<int, int>> st;

7 st.push({start, 0});

8 parent[start] = 0;

9 while (!st.empty()) {

10 int p = st.top().first;

11 int d = st.top().second;

12 st.pop();

13 distance[p] = d;

14 for (int c : adj[p])

15 if (distance[c] == -1) {

16 parent[c] = p;

17 st.push({c, d + 1});

18 }

19 }

20 }

21

22 int profit(int start, vector<int> &amount) {

23 stack<pair<int, int>> st;

24 st.push({start, 0});

25

26 int maxi = INT_MIN;

27 while (!st.empty()) {

28 int count = 0;

29 int root = st.top().first;

30 int value = st.top().second + amount[root];

31 st.pop();

32

33 visited[root] = true;

34 for (int c : adj[root])

35 if (!visited[c]) {

36 count++;

37 st.push({c, value});

38 }

39 if (!count) maxi = max(value, maxi);

40 }

41

42 return maxi;

43 }

44

45 public:

46 int mostProfitablePath(vector<vector<int>> &edges, int bob, vector<int> &amount) {

47 int size = amount.size();

48 adj.resize(size, vector<int>());

49 distance.resize(size, -1);

50 parent.resize(size, -1);

51 visited.resize(size, false);

52

53 for (auto &e : edges) {

54 adj[e[0]].push_back(e[1]);

55 adj[e[1]].push_back(e[0]);

56 }

57

58 distance_parent(0);

59

60 for (int current = bob, bob_distance = 0; current; bob_distance++) {

61 if (distance[current] > bob_distance)

62 amount[current] = 0;

63 else if (distance[current] == bob_distance)

64 amount[current] /= 2;

65 current = parent[current];

66 }

67

68 return profit(0, amount);

69 }

70 };