The question is something like this,

Given a list of edges, find a path from SRC to DEST that gives the highest points. INPUT: [['A', 'B', 5] , ['A', 'C', 2], ['B', 'C', 5]], find path from A to B. OUTPUT: ['A', 'C', 'B'], which gives 10 points.

I understand this is a graph problem, one way to solve it will be DFS with backtracking whereby we try out all the options that lead us from A to B, and record the one with the highest score. The time complexity for this will probably be N! in a fully connected graph, since we are trying all permutations.

However, I think we can optimise it by pruning while backtracking. E.g. We keep track of the highest points we can get at each node. If the current point is less than the existing highest point, we don't have to try anymore.

But I can't quite figure out the time complexity for this with pruning. Will the worst case still be N! since we can technically still do all permutations?