Ciel and Random Walk
All submissions for this problem are available.
Today, Ciel's restaurant is closed.
Ciel is bored, so she decides to take a walk randomly.
This town has N intersections and M one way roads.
The i-th road connects from the Ai-th intersection to the Bi-th intersection.
Ciel is in the 1st intersection now, and Ciel's house is in the N-th intersection.
If Ciel is in the i-th intersection, she will take a walk as follows:
- If i = N, her walk is ended.
- Otherwise, she chooses an integer k such that Ak = i uniformly randomly, she walks along the k-th road.
On the way, S intersections have beautiful flowers.
Let the F1-th intersection, the F2-th intersection, ..., and the FS-th intersection have beautiful flowers.
Can you tell the probability that Ciel last sees the flowers in the Fi-th intersection?
That is to say, can you tell the probability that she visits the Fi-th intersection, then she goes to N-th intersection without visiting other intersections having beautiful flowers?
The first line contains 3 integers N, M and S.
Then, next line has S integers F1, F2, ..., FS.
Next M lines have 2 integers each, Ai and Bi.
An output should contain S lines.
In the i-th line, print the probability that Ciel last sees beautiful flowers at the Fi-th intersection.
These values must have an absolute error no more than 10-6.
1 ≤ S < N ≤ 30
1 ≤ F1 < F2 < ... < FS < N
Ai ≠ Bi
If i ≠ j and Ai = Aj, then Bi ≠ Bj
For each 1 ≤ i < N, Ciel can go from the i-th intersection to the N-th intersection, directly or indirectly.
Sample Input 1
4 6 3 1 2 3 1 2 2 1 1 3 3 1 2 4 3 4
Sample Output 1
0 0.5 0.5
Sample Input 2
4 6 1 2 1 2 2 1 1 3 3 1 2 4 3 4
Sample Output 2
Sample Input 3
2 1 1 1 1 2
Sample Output 3
The sum of output values can be less than 1, because Ciel may go back to her house without seeing beautiful flowers.
|Tags||cook17, hard, laycurse|
|Time Limit:||0.345763 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.