Saying Hello

All submissions for this problem are available.
Once upon a time, Bob decided to say ‘Hello’ to Alice. Knowing that Alice had a soft corner for bicyclists, he took out his bike and decided to cycle to Alice’s home.
Now, the hometown of Alice and Bob  the MathLand, is a very scenic location, hidden somewhere in the Himalayas. Bob being a lover of scenic sights and integer sequences, rated scenery of roads on a weird scale of first 6 Super Awesome Numbers, viz. 3,4,6,12,16,18. Whenever at any crossroad C, Bob selects a road i having rating R(i) with probability P(i/C) = R(i) / (∑(R(j)) where summation is over all j roads from C (including the road from which he reached crossroads, irrespective of the location of Alice’s home). Bob proceeds thus, till he reaches Alice’s home. After meeting Alice and saying ‘Hello’ (and having a delicious pudding made by Alice, but miraculously all of these taking 0 time!), Bob heads back home in similar fashion.
There are N crossroads in MathLand. Alice’s and Bob’s home are near(at) 1st and Kth crossroads respectively. All roads in MathLand are bidirectional. Between any two given (distinct) crossroads, there is atmost 1 (direct) road. The time taken to travel from crossroad i to crossroad j is given by Tij. Now MathLand is situated over mountains of Himalayas and Bob is driving a bicycle, so because of slopes, the time taken to reach crossroad i from j on the road connecting them need not be same as that of j to i (though the rating of roads is same for both directions).
Your task is very simple. You have to find the expected time of this ‘outing’ of Bob.
Input Format
 There are several test cases.
 Each test case beginning with a single line containing 3 space separated integers  N,M,Q denoting number of crossroads, number of roads in MathLand and Q possible locations of Alice’s home.
 M lines follow, each containing 5 space separated integers U,V,R,Tuv,Tvu, denoting a road, its rating and ‘toandfro’ timings.
 Q lines follow, each containing a single integer K, denoting the location of Alice’s home.
 File ends with a single line containing N=M=Q=0 which should not be processed.
Output Format
 For every test case output a single line denoting case number.
 Then Q lines, each denoting the time for each K of that case.
 Print this expected time, rounded to exactly four places after decimal point. Note that, atmost an error of 1e3 is tolerated by the judge.
 Print INFINITE if this expected time of reaching Alice’s home or coming back (or both) is infinite.
Constraints
 N >=2
 Sum(N) over all test cases <= 50
 0<= M <= MIN(100,(N*(N1))/2)
 0<= Q <=N
 R ∈ {3,4,6,12,16,18}
 1<= U,V <=N
 1<= Tij <=1000
 1<=K <=N
Sample Input
4 2 3
1 2 3 2 1
1 3 3 3 1
1
2
4
0 0 0
Sample Output
Case #1:
0.0000
7.0000
INFINITE
Explanation
Explanation of Test Case#1:
When K=2,
Expected time of 1 > 2 travel:
S_12 = ½(2) + ¼(6) + ⅛(10) + 1/16(14) + 1/32(18) + …
Solving this AGP, S_12 = 6
Expected time of 2>1 travel:
S_21 = 1(1) = 1
So, expected time of the complete outing = S_12 + S_21 = 7
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  28022014 
Time Limit:  10 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions