how to solve this SPOJ problem ? Is my way correct?

Правка en1, от realloc_anh1l1ator, 2015-08-15 11:40:26

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?

Теги dfs, floyd-warshall, graph-theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский realloc_anh1l1ator 2015-08-15 11:40:26 579 Initial revision (published)