All submissions for this problem are available.
In real life, Amy and Blanchett are great friends. They want to celebrate the Blanchett's victory for winning Best Actress Oscars Award.
They love to travel by trains. So,they planned to visit Metro Land. It consists of n stations connected by m railway tracks. Between two stations there is a single two-way track. All stations are reachable from each other.
As Amy and Blanchett’s homeplaces are very far from each other , they reached the Disney Land directly at stations i and j respectively.But Amy forgot her phone at home, so they were unable to contact each other.
In the hope of meeting each other luckily, both of them followed a strategy.
At each station i, Amy or Blanchett can decide to stay there with probability pi or can decide to move with probability (1-pi) by choosing one of the tracks going from station i with equal probability.
E.g. If total l tracks go from station i, then they can choose the track going to station j with probability (1-pi)/l.
Your task is to help two friends in meeting each other by finding the probability of their meeting at each station
The first line contains four integers: n representing the numbers of stations. m representing the number of tracks. i , j representing the starting stations of Amy and Blanchett respectively.
Next m lines contain pairs of numbers — the numbers of stations connected by a track.
Next n lines contain probabilities pi with the accuracy of up to two digits after the decimal point — the probability to stay at station i.
In the n lines print n numbers, the number on ith line should represent the probability that the friends meet at the ith station rounded upto 6 decimal places.
- 1 ≤ n ≤ 20
- n-1 ≤ m ≤ (n*(n-1))/2
- 1 ≤ i,j ≤ n (i and j can be equal.)
- 0.01 ≤ pi ≤ 0.99
Sample Input 1: 3 3 1 1 1 2 2 3 3 1 0.50 0.50 0.50 Sample Output 1: 1.000000 0.000000 0.000000 Sample Input 2: 3 3 1 2 1 2 1 3 2 3 0.50 0.50 0.50 Sample Output 2: 0.357143 0.357143 0.285714
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, GO, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.