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).