Given a directed acyclic graph with N nodes and M edges having positive weights, increase the edge weights of some edges such that the total weight (sum of edge weights on the route) of any route from 1 node to N node is same and minimum. Following are the constraints:

The total weight of all the possible routes from 1 node to Nth node should be same and minimum.

Weight of only one edge on a possible route can be increased.

In case of multiple solutions for a route, choose the edge closer to destination (Nth node).

Print “No Solution” if it is not possible.

For example:

N=6

M=8

Edges are:

1->4=7

1->5=12

2->3=4

2->4=2

3->6=6

4->6=8

5->6=10

Here i->j=c means edge from ith node to jth node with weight c.

Answer:

3->6=10

2->4=6

1->4=14

This would make the total weight=22 for all possible paths from 1 to N.

My approach:

I made a list of all the possible paths from 1 to N, maintaining their total weight as well.

I also maintained a variable with maximum.

Also I maintained a list of edge occurrences (edge and no. of times it came in the paths from 1 to N).

Then I traversed this list and whichever edge had 1 occurrence, I checked if any edge closer to destination with 1 edge exists or not. If it does, I increased its weight to match with maximum and then removed all edges on this path from my list and updated the total weight of the path.

I repeated this in a loop.

But the submission gave me “Wrong Answer”.

I would like to know where I went wrong or a different approach to this problem (with or without code).