I came across this problem while giving a sample test.
The problem was that we have given a tree which is undirected. We can start from any node of our choice. Initially we have power "P" and while going from one node to other node we loose some power "X" (consider as cost of travelling) and earn some profit "Y". So we need to tell that what is the maximum profit that we can earn with a given power ? Every node can be visited only once.
Example: First line contains number of nodes and initial power
Next n-1 lines contains node-node-cost-profit
1 2 1 2
1 3 2 3
1 4 2 4
4 5 2 2
Answer => 7. We can start from 4 and go to 1 and than to 3.
I have applied DFS on this to get maximum profit earned by traversing every single path.
But is there a way to decrease time ??? Can we apply floyd warshall algorithm to calculate distances each edges ??
from collections import defaultdict class tree: def __init__(self,nodes): self.nodes = nodes self.graph = defaultdict(list) def add(self,a,b,charge,profit): self.graph[a].append([b,charge,profit]) self.graph[b].append([a,charge,profit]) def start(self,power): maxi = -1 visited = [False for i in range(self.nodes)] for i in range(1,self.nodes+1): powers = power visited[i-1] = True for j in self.graph[i]: temp = self.dfs(j,powers,0,visited) if temp > maxi: maxi = temp visited[i-1] = False return maxi def dfs(self,node,powers,profit,visited): v,p,pro=node,node,node if powers-p < 0: return 0 if powers-p == 0: return profit + pro profit += pro powers = powers-p visited[v-1] = True tempo = profit for k in self.graph[v]: if visited[k-1] == False: temp = self.dfs(k,powers,tempo,visited) if temp > profit: profit = temp visited[v-1] = False return profit t = tree(5) t.add(1,2,1,2) t.add(1,3,2,3) t.add(1,4,2,4) t.add(4,5,2,2) print(t.start(4))