Need help with a graph problem

I can't see a way to do this except for an exhaustive search (depth-first recursion) from the starting point.

Exclude an edge when it has already been traversed in the same direction. When you can't add another edge, compare the number of vertices in the current walk with the number in the best walk so far. If the current walk reached more, it becomes the candidate solution. If it reached the same number, it becomes the candidate if its cost is less.

A walk ends when it (a) cannot add another edge without exceeding the maximum cost or (b) has reached all vertices.

When you back up to a previous vertex, the edge in question becomes available again in the original direction.

If you display what your program is doing during its search, you may find some optimizations. But without writing the code, I can't think of any.

Quote:

I will really appreciate it if you solve this problem with C++

Do you understand that you are basically required to create a solution by- yourself ?
And not necessarily the optimum algorithm.

Quote:

Someone said to me that the problem can be solved with simple Dijkstra Search, but I don't see how the shortest path between two nodes can solve this problem.

As far as I understand, it is not "Dijkstra shortest path" algorithm.