MRPATH - Most Reliable Path

no tags 

 

A communication network is represented as a cycle-free, not necessarily simple, weighted, directed graph. The weight, r(e), of an edge e is a real number in the interval [0, 1] representing the reliability of the communication channel represented by the edge. The reliability of a communication channel is interpreted as the probability that the channel will not fail. We assume that all probabilities are independent. There could be more than one channel between the same two nodes, in the same direction. Give an efficient algorithm to find the most reliable path from a given source node to a given destination node. What is the worst-case time complexity of your algorithm?

Input

The first line of input will contain the number of nodes in the network N and the number of edges in the network E (2 <= N, E <= 30,000).

The second line of input will contain s and d, the source and the destination.

Each of the next E lines will contain ab, c  (1 <= a, b <= N, 0 <= c <= 1), indicating that there is a directed edge from node a to node b with reliability c.

Output

Print to the ouput a single floating point number r, denoting the reliability of the best path from s to dr should contain exactly 6 digits after the decimal point.

Example

Input:

4 6
1 4
1 2 0.75
1 2 0.5
2 3 1
2 4 0.75
1 3 1.0
3 4 0.25

Output:

0.562500

hide comments
wertzu: 2015-06-14 14:10:18

Easy one :D

hossam: 2011-12-27 14:20:48

Can't we have more test cases?


Added by:Atef
Date:2011-12-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C++ 4.3.2 CPP JAVA
Resource:Introduction to Algorithms (CLRS)