The Unconscious Hide And Seek
Statement
Goal
Background(Not necessary)In the Palace of the Earth Spirits(Chireiden),an ordinary day.
Little crow Okuu was doing ordinary nuclear fusion，to kept the temperature of the subterranean world.
When the owner of the Chireiden,Satori,finished her daily works,she met her younger sister Koishi who was going home from the ground world.
The sisters had nothing to do,so they decided to play a game called "The Unconscious Hide And Seek".
It's called "Hide and Seek",however,it's totally different with normal hide and seek game,it's more like "Game Of Tag" ---- Satori and Koishi stand in different place at the start,Satori win when she catches Koishi.
But why called "Hide and Seek" ?
That's because koishi can do actions "unconsciously",which means she is "invisible",can't be noticed.
That's really an interesting ability.
Satori's pet cat Orin standed near by,deeply lost in thought.
This is the story of "The Unconscious Hide And Seek",it happened few days ago.
Of course,Orin didn't got that point.
Gradually,the cat no longer think about it,she wants to play "The Unconscious Hide And Seek" too.
However,in this subterranean world,except the owner's younger sister Koishi,no one can hide his/her existence.
So,a new game comes up...
This is the story beside "The Unconscious Hide And Seek".
Description
The game is played on a N nodes,M edges directed acyclic graph.
At the
Since the
They take there actions at the same time,and we consider that the action takes no time.
When Orin is caught by Okuu,the game ends immediately.If Okuu never catches Orin,they should not move AFTER the Tth second.The game will end at T+1th second.
Okuu's goal is to catch up Orin as fast as she can(Catch up means they stand in the same node),and Orin's goal is to live longer.
Specifically,if a game ends at
We consider that in the whole game,Orin and Okuu always know the position of each other.In the
Koishi wants to know the expected value of the second when the game ends,if both orin and okuu take best movements.
Input
Line 1:Five space separated integers N,M,Sr,Sk,T.
Next M lines:Two space separated integers A and B,means there is a directed edge from A to B.
Next M lines:Two space separated integers A and B,means there is a directed edge from A to B.
Output
Line 1 : The answer,a number,rounded off to three decimal places.
Constraints
For 69.2% cases, 0≤n≤3。
For 100% cases, 0≤n,t≤20。
For 100% cases, 0≤n,t≤20。
Example
Input
3 2 1 2 10 1 3 2 3
Output
11.000
Tags
Dynamic programming, Linear programming, Game theory
Difficulty
Very Hard
Test cases
Sample Test
Input
3 2 1 2 10
1 3
2 3
Output
11.000
Sample Test Validator
Input
3 2 2 1 9
1 3
2 3
Output
10.000
1-2,2-3,1-3 Case Test
Input
3 3 1 2 6
2 1
2 3
1 3
Output
1.857
1-2,2-3,1-3 Case 2 Validator
Input
3 3 2 1 2
1 2
2 3
1 3
Output
1.667
Directly Catch Test
Input
3 2 2 1 4
1 2
2 3
Output
2.000
Directly Catch 2 Validator
Input
3 2 2 1 1
1 2
2 3
Output
2.000
Which Way Test
Input
3 2 2 1 3
1 2
1 3
Output
1.000
Which Way 2 Validator
Input
3 2 3 1 2
1 2
1 3
Output
1.000
No Time Test
Input
3 3 1 2 0
1 2
2 3
1 3
Output
1.000
No Time And Same Place Validator
Input
3 3 2 2 0
1 2
2 3
1 3
Output
0.000
Same Place Test
Input
3 3 1 1 3
1 2
2 3
1 3
Output
0.000
Same Place 2 Validator
Input
1 0 1 1 9
Output
0.000
One Way Test
Input
2 1 2 1 1
1 2
Output
1.000
One Way 2 Validator
Input
3 1 2 1 9
1 2
Output
1.000
Can't Reach Test
Input
3 1 2 1 9
2 1
Output
10.000
Can't Reach 3 Validator
Input
3 1 2 1 8
2 3
Output
9.000
Can't Reach 2 Test
Input
2 0 2 1 7
Output
8.000
Can't Reach 4 Validator
Input
3 2 2 3 17
1 2
2 3
Output
18.000
Large Map 1 Test
Input
6 8 2 1 2
1 2
1 3
1 5
2 3
3 5
5 6
6 4
2 4
Output
2.333
Large Map 4 Validator
Input
5 10 2 1 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output
2.710
Large Map 2 Test
Input
6 7 1 6 20
6 1
1 2
1 3
2 4
2 5
3 4
3 5
Output
3.000
Large Map 5 Validator
Input
6 10 3 1 4
1 3
3 2
2 4
1 5
5 6
6 4
3 5
3 6
5 2
6 2
Output
3.071
Large Map 3 Test
Input
8 16 2 1 5
1 2
2 3
3 4
4 5
5 6
6 7
1 3
3 5
5 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
Output
3.201
Large Map 6 Validator
Input
9 11 2 1 5
1 2
2 3
2 4
3 5
4 5
2 5
5 6
6 7
6 8
6 9
7 9
8 9
Output
4.667
Very Large Map Test
Input
20 27 2 1 20
1 2
2 3
3 4
3 5
3 6
5 7
5 8
5 9
5 10
6 10
6 9
7 11
8 12
9 13
10 14
11 15
12 15
13 15
14 16
15 17
15 18
16 17
16 18
17 18
18 19
19 20
16 20
Output
9.471
Very Large Map 2 Validator
Input
20 190 2 1 20
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
10 11
10 12
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 20
11 12
11 13
11 14
11 15
11 16
11 17
11 18
11 19
11 20
12 13
12 14
12 15
12 16
12 17
12 18
12 19
12 20
13 14
13 15
13 16
13 17
13 18
13 19
13 20
14 15
14 16
14 17
14 18
14 19
14 20
15 16
15 17
15 18
15 19
15 20
16 17
16 18
16 19
16 20
17 18
17 19
17 20
18 19
18 20
19 20
Output
8.409
Solution language
Solution
Stub generator input