Spoj... You are given a acyclic directed graph with each edge having probability of success. You are also given two nodes start and end !

What is the maximum probability to reach from starting point to End.?

What I am trying is :

1) Remove redundant edges with same source and destination and put the edge with maximum probability instead. 2) Topological Sort the Graph. 3) Calculate the probability starting from S.

I am only getting 50 points . Am I wrong somehwere?

I was trying Problem and was unable to understand the complexity analysis.

Morover , there is not much detailed explanation on google! Can someone help? What I think the steps in such a problem is :

1) Define a state that represents the whole situation of a system ( LIke in DP) 2) Define some transitions (Each transition should have same weight ) 3) Search for the state applying some constraints!

But I cannot understand the Complexity analysis too!

Morover my code here gives TLE on the same problem 12483335 Can someone explain?

Please !!