Hi Guys!

I'm back, with another problem! Link! I have tried to debug for 3 days now to no avail :'( ... so I'd be a really happy if some of you could help :D

Anyways, on to the algo:

I first toposorted the data, and maintained 2 DPs:

dp[i][0] = minimum length to make all paths from topo[i] to topo[n] the same length without any tolls (on any path)
dp[i][1] = minimum length to make all paths from topo[i] to topo[n] the same length with at most 1 toll (on some path)

So the transition seems something like this:

dp[i][0] = dp[j][0] if all the d(i, j) + dp[j][0] are the same (j is a child of i)
dp[i][0] = MAX otherwise (impossible)

Now, for dp[i][1], let's consider j's that are children of i. For some j, if dp[j][0] is not MAX (it's possible to do), then let's add (dp[j][0], 0) to a vector. Otherwise, if dp[j][1] is not MAX, let's add (dp[j][1], 1). Now, let's sort the vector and find the maximum dp value. This represents the final length of the road. But for the other values, if the dp value is less than the final length and it came from a dp[some][1], then we stop, and dp[i][1] = INF. Else, dp[i][1] = the max dp value.

I have the code here, but it's wrong:

Code

I am aware that if there is a solution, the overall price for each path will be the longest path from start to end in the graph. I used this to try to debug, but it didn't help.

I have some test cases here, but the ones that fail are really big. (Also, I just completely ignored the "printing fares" part, because my calculation of the final path length is incorrect for many cases)