oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

forkintheroad Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

forkintheroad.html

forkintheroad

Problem Statement

There is a cave consisting of N rooms and M one-directional passages. The rooms are numbered 1 through N.

Takahashi is now in Room 1, and Room N has the exit. The i-th passage connects Room si and Room ti (si < ti) and can only be traversed in the direction from Room si to Room ti. It is known that, for each room except Room N, there is at least one passage going from that room.

Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room 1 at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.

Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room 1. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room N.

Let E be the expected number of passages Takahashi takes before he reaches Room N. Find the value of E when Aoki makes a choice that minimizes E.

Constraints

  • 2 ≤ N ≤ 600
  • N-1 ≤ M ≤ N(N-1)/2
  • si < ti
  • If i != j, (si, ti) ≠ (sj, tj). (Added 21:23 JST)
  • For every v = 1, 2, ..., N-1, there exists i such that v = si.

Input

Input is given from Standard Input in the following format:

N M
s1 t1
:
sM tM

Output

Print the value of E when Aoki makes a choice that minimizes E. Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10-6.

Sample Input 1

4 6
1 4
2 3
1 3
1 2
3 4
2 4

Sample Output 1

1.5000000000

If Aoki blocks the passage from Room 1 to Room 2, Takahashi will go along the path 1 → 3 → 4 with probability \frac{1}{2} and 1 → 4 with probability \frac{1}{2}. E = 1.5 here, and this is the minimum possible value of E.

Sample Input 2

3 2
1 2
2 3

Sample Output 2

2.0000000000

Blocking any one passage makes Takahashi unable to reach Room N, so Aoki cannot block a passage.

Sample Input 3

10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9

Sample Output 3

3.0133333333

Tags

AtCoder, Math, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100652s256MBMinimum
2032s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o forkintheroad -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.