The Triwizard Tournament
All submissions for this problem are available.
The Triwizard Tournament was established roughly seven hundred years ago as a friendly competition amond the wizarding schools viz., the Hogwarts School of Witchcraft and Wizardry, the Beauxbatons Academy of Magic and the Durmstrang Institute. Held every five years, the competition would be hosted by each school in turn, the judges for the Tournament comprising the headmasters and headmistresses of the schools.
The last Triwizard Tournament ended with many sad memories. To honour the memory of all those who were lost in the last tournament, it has been decided that Hogwarts will be hosting the Triwizard Tournament again this year.
Professor Dumbledore wants to introduce a new event this time. This event was suggested to him by Hermione Granger. In this event, a dear friend of each of the champions would be left blindfolded in some cell of the Dungeons, beneath the Hogwarts Castle. This friend has to start from the cell where he/she was left and come out of the Dungeons while walking through other cells and corridors he/she finds on his/her way. If he/she is unable to come out, then he/she would be consumed by the snakes hiding in the dungeons.
Description of dungeons: Dungeons can be viewed as a graph in which the cells of the dungeons are the nodes and the corridors between the cells are the edges of the graph. The time needed to cross a path is the weight of the edges of the graph.
To add to the difficulty of the task, no magic is allowed inside the Dungeons. Thus, the friend of any champion would need to rely on his/her instincts and luck. It turns out that when you are in a cell of the Dungeons, the best strategy for escape is to randomly choose an edge to one the neighbouring cells. This way, you can increase your chances of escaping the Dungeons. You are asked to report the expected time one would take to escape the Dungeons starting from the initial cell where he/she was left. Assume that the friend uses the escape strategy as described above.
The first line of the input contains a single integer T, the number of test cases.
The first line of each test case contains four space separated integers N M S E where
- N: Number of cells in the dungeons
- M: Number of edges between the pairs of cells
- S: The Starting Cell
- E: The Destination Cell
This is followed by M lines each containing three space separated integers X Y W which denotes that W is the time required to cross the corridor from cell X to cell Y and also from cell Y to cell X.
A single line for each test case which contains a single floating point number K, the expected time to come out of the dungeon. K must be rounded upto 6 places after the decimal.
- 1 ≤ T ≤ 25
- 2 ≤ N ≤ 200
- 0 ≤ S,D,X,Y ≤ N-1
- 1 ≤ W ≤ 100
Assume that it is always possible to escape the Dungeons, i.e. you can always reach D from S.
Input: 2 2 1 0 1 0 1 42 3 3 0 2 0 1 1 0 2 2 1 2 3 Output: 42.000000 3.333333
|Time Limit:||0.3225 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions