At the end of the Middle Ages, quite a few universities throughout Europe have already been founded.
The new term has just begun, so there are a lot of freshmen around. Not everyone has been lucky
to be admitted to her/his desired university. As a result, many couples are now living in separate
towns.
Of course, they try to see each other as often as they can. To facilitate this, the students have
negotiated a deal with the coachmen. Instead of paying the regular price for a ride from one town
to another, the price is determined by drawing a random integer between 1 and R inclusive, all
numbers being equally likely. Unfortunately, this process repeats itself a few times whenever there
is no direct connection between the towns a couple lives in. That makes the total cost of a journey
quite unpredictable.
Help the couples determine the probability that one of them can afford a one-way trip to the other
one. Given the number of towns and a list of direct connections, your program is supposed to process
a list of couples. For each couple, you know their budget and where they live. Of course, they will
always choose a route with the least expected price. Such a route exists between any two towns.
The first line contains the number of test cases that follow.
Each test case begins with a line that holds the number N of towns (1 ≤ N ≤ 100) followed by the
maximum price R of a single ticket (1 ≤ R ≤ 30). The following N lines contain N characters each.
The j-th character in the i-th line of these is “Y” if there is a direct connection between towns i and
j, but “N” otherwise. The j-th character in the i-th line is always the same as the the i-th character
in the j-th line. The j-th character in the j-th line is always “N”.
Each test case goes on with the number C of couples on a line by itself (1 ≤ C ≤ 1000). Then for
each couple there is a line that holds three integers a, b, and m. These numbers state that one of
them lives in town a, the other one in town b (1 ≤ a, b ≤ N , a != b), and the amount of money they
can spend is m (1 ≤ m ≤ 10000).
For each test case, print one line containing the word “Case”, a single space, and its serial number
(starting with 1 for the first test case). Then, output one line for each couple in this test case
containing the probability that they can afford a one-way journey according to the rules above. Please output the answer rounded off to 3 digits after the decimal point. Print a blank line after each test
case.
2 3 4 NYY YNY YYN 1 1 3 1 4 7 NYNN YNYN NYNY NNYN 2 1 3 10 1 4 10
Case 1 0.250 Case 2 0.796 0.341
Migrated from old NTUJ.
SWERC 2008
| No. | Testdata Range | Score |
|---|