Problem:
 Score : 600 points    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 s_i and Room t_i ( s_i < t_i ) and can only be traversed in the direction from Room s_i to Room t_i . 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 \leq N \leq 600  N-1 \leq M \leq \frac{N(N-1)}{2}  s_i < t_i  If i != j , (s_i, t_i) \neq (s_j, t_j) . (Added 21:23 JST)  For every v = 1, 2, ..., N-1 , there exists i such that v = s_i .         Input Input is given from Standard Input in the following format:  N  M  s_1  t_1  :  s_M  t_M       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

Solution (Python):


import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)

Solution (Python):

import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	
rev_al=[ [] for i in range(N+1) ]	
I=[ 0 for i in range(N+1) ] 
O=[ 0 for i in range(N+1) ] 
edge=[] 
I[0]=None

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    I[t]+=1
    O[s]+=1
    edge.append((s,t))


L=[]
q=deque()
for x in range(N):
    if I[x]==0:
        q.append(x) 

while q:
    fro=q.popleft()
    L.append(fro)
    for to in al[fro]:
        I[to]-=1
        if I[to]==0:
            q.append(to)

if len(L)!=N:
    prin


P=[ 0 for i in range(N+1) ]   
P[1]=1

for x in L:
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        

E=[ 0 for i in range(N+1) ]   

for x in L[::-1]:
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p

ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

Solution (Python):

import sys

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	
rev_al=[ [] for i in range(N+1) ]	
O=[ 0 for i in range(N+1) ] 
edge=[] 

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    
    O[s]+=1
    edge.append((s,t))



P=[ 0 for i in range(N+1) ]   
P[1]=1
 
for x in range(1,N+1):
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        

E=[ 0 for i in range(N+1) ]   

for x in range(N,0,-1):
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p



ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

Solution (Python):

import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	
rev_al=[ [] for i in range(N+1) ]	
O=[ 0 for i in range(N+1) ] 
edge=[] 

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    
    O[s]+=1
    edge.append((s,t))



P=[ 0 for i in range(N+1) ]   
P[1]=1
 
for x in range(1,N+1):
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        

E=[ 0 for i in range(N+1) ]   

for x in range(N,0,-1):
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p



ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

Solution (Python):

import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	
rev_al=[ [] for i in range(N+1) ]	
O=[ 0 for i in range(N+1) ] 
edge=[] 

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    
    O[s]+=1
    edge.append((s,t))



P=[ 0 for i in range(N+1) ]   
P[1]=1
 
for x in range(1,N+1):
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        

E=[ 0 for i in range(N+1) ]   

for x in range(N,0,-1):
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p



ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
ST = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for s, t in ST:
    graph[s].append(t)






dp = np.full((N + 1, N + 1), IINF, dtype=float)
dp[N] = 0.0
for v in reversed(range(1, N)):
    
    dp[v, :] = dp[graph[v], :].sum(axis=0) / len(graph[v]) + 1
    if len(graph[v]) >= 2:
        
        s = dp[graph[v], v].sum() - dp[graph[v], v].max()
        dp[v, v] = s / (len(graph[v]) - 1) + 1
print(dp[1].min())

Solution (Python):
def f_fork_in_the_road():
    
    N, M = [int(i) for i in input().split()]
    Nodes = [[int(i) for i in input().split()] for j in range(M)]

    edges = [[] for _ in range(N)]
    for s, t in Nodes:
        edges[s - 1].append(t - 1)

    
    probability = [0] * N
    probability[0] = 1.0
    for v in range(N):
        for next_vertex in edges[v]:
            probability[next_vertex] += probability[v] / len(edges[v])

    
    expected_value = [0] * N
    for v in range(N - 2, -1, -1):
        for next_vertex in edges[v]:
            expected_value[v] += expected_value[next_vertex]
        expected_value[v] = 1 + expected_value[v] / len(edges[v])

    ans = expected_value[0]
    for v in range(N):
        if len(edges[v]) <= 1:
            continue
        
        
        v_max_expected = max(((expected_value[w], w) for w in edges[v]))[1]
        expected_diff = 0.0
        outdegree = len(edges[v])
        for next_vertex in edges[v]:
            if next_vertex == v_max_expected:
                expected_diff -= expected_value[next_vertex] / outdegree
            else:
                expected_diff += expected_value[next_vertex] / (outdegree * (outdegree - 1))
        ans = min(ans, expected_value[0] + probability[v] * expected_diff)
    return round(ans, 10)

print(f_fork_in_the_road())

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
v = [[] for _ in range(N)]
for i in range(M) :
    s, t = map(int, input().split())
    v[s-1].append(t-1)


dp = [0] * N
for i in range(N - 1, -1, -1) :
    if len(v[i]) == 0 :
        continue
    
    for j in v[i] :
        dp[i] += dp[j]
    dp[i] = 1 + dp[i] / len(v[i])
    
ret = dp[0]

for i in range(N - 1) :
    if len(v[i]) <= 1 :
        continue
        
    dp[i] = 0
    M = -1
    for j in v[i] :
        dp[i] += dp[j]
        M = max(M, dp[j])
    dp[i] = 1 + (dp[i] - M) / (len(v[i]) - 1)
    
    for j in range(i - 1, -1, -1) :
        if len(v[j]) == 0 :
            continue
            
        dp[j] = 0
        for k in v[j] :
            dp[j] += dp[k]
        dp[j] = 1 + dp[j] / len(v[j])
    
    ret = min(ret, dp[0])

print(ret)

Solution (Python):

N,M = list(map(int,input().split()))

e_list = [[] for i in range(N)]

for i in range(M):
    s,t = list(map(int,input().split()))
    s,t = s-1,t-1
    e_list[s].append(t)

DP = [0 for i in range(N)]
dp0_min = 10**27

for x in range(N-1):
    for i in range(N-1):
        if i==x:
            if len(e_list[N-i-2])==1:
                DP[N-i-2] = DP[e_list[N-i-2][0]]+1
            else:
                max_room = -1
                max_path = 0
                for j in e_list[N-i-2]:
                    if max_path<DP[j]:
                        max_room = j
                        max_path = DP[j]
                    DP[N-i-2] += DP[j]
                DP[N-i-2] -= DP[max_room]
                DP[N-i-2] /= len(e_list[N-i-2])-1
                DP[N-i-2] += 1
        else:
            for j in e_list[N-i-2]:
                DP[N-i-2] += DP[j]
            DP[N-i-2] /= len(e_list[N-i-2])
            DP[N-i-2] += 1
    dp0_min = min(dp0_min,DP[0])
    DP = [0 for i in range(N)]
print(dp0_min)

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    N,M = list(map(int,input().split()))

    e_list = [[] for i in range(N)]

    for i in range(M):
        s,t = list(map(int,input().split()))
        s,t = s-1,t-1
        e_list[s].append(t)

    DP = [0]*N
    dp0_min = 10**27

    for x in range(N-1):
        for i in range(N-1):
            if i==x:
                if len(e_list[N-i-2])==1:
                    DP[N-i-2] = DP[e_list[N-i-2][0]]+1
                else:
                    max_room = -1
                    max_path = 0
                    for j in e_list[N-i-2]:
                        if max_path<DP[j]:
                            max_room = j
                            max_path = DP[j]
                        DP[N-i-2] += DP[j]
                    DP[N-i-2] -= DP[max_room]
                    DP[N-i-2] /= len(e_list[N-i-2])-1
                    DP[N-i-2] += 1
            else:
                for j in e_list[N-i-2]:
                    DP[N-i-2] += DP[j]
                DP[N-i-2] /= len(e_list[N-i-2])
                DP[N-i-2] += 1
        dp0_min = min(dp0_min,DP[0])
        DP = [0]*N
    print(dp0_min)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
st=[list(map(int,input().split())) for i in range(M)]
way=[[] for i in range(N)]
for s,t in st:
    way[s-1].append(t-1)
dp=[0]*N
dp_reducable=[0]*N
pr=[0]*N
pr[0]=1
for i in range(N-1,-1,-1):
    l=len(way[i])
    if l>1:
        MAX=0
        x=0
        for j in way[i]:
            x+=dp[j]
            if dp[j]>MAX:
                MAX=dp[j]
        x_r=(x-MAX)/(l-1)+1
        x=x/l+1
        x_r=x-x_r
    elif l==0:
        continue
    else:
        x=dp[way[i][0]]+1
        x_r=0
    dp[i]=x
    dp_reducable[i]=x_r
    i=N-1-i-1
    l=len(way[i])
    for j in way[i]:
        pr[j]+=pr[i]/l
print(dp[0] - max(p * r for p, r in zip(pr, dp_reducable)))

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
graph_dim_out = [0] * n
for i in range(m):
    s, t = map(int, input().split())
    s, t = s - 1, t - 1
    graph_dim_out[s] += 1
    graph[s].append(t)


def func(x):
    dp = [0] * n
    for i in reversed(range(n - 1)):
        if i != x or graph_dim_out[x] == 1:
            for j in graph[i]:
                dp[i] += dp[j]
            dp[i] = dp[i] / graph_dim_out[i] + 1
        else:
            k = -1
            for j in graph[i]:
                dp[i] += dp[j]
                if k == -1 or dp[k] < dp[j]:
                    k = j
            dp[i] -= dp[k]
            dp[i] = dp[i] / (graph_dim_out[i] - 1) + 1

    return dp[0]


ans = func(0)
for x in range(1, n - 1):
    ans = min(ans, func(x))

print(ans)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    to = defaultdict(list)
    ot = defaultdict(list)
    for _ in range(m):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        to[s].append(t)
        ot[t].append(s)
    
    
    ev = [0] * n
    for u in range(n - 2, -1, -1):
        s = 0
        for ku in to[u]:
            s += ev[ku]
        ev[u] = s / len(to[u]) + 1
    
    
    pe = [[0] * n for _ in range(n)]
    
    pn = [0] * n
    
    for u in range(n):
        p = 0
        for ou in ot[u]:
            p += pe[ou][u]
        if u == 0: p = 1
        pn[u] = p
        sz = len(to[u])
        for ku in to[u]:
            pe[u][ku] = p / sz
    
    
    dx = 0
    for u in range(n - 1):
        sz = len(to[u])
        if sz == 1: continue
        mx = 0
        for ku in to[u]:
            mx = max(ev[ku], mx)
        nev = ((ev[u] - 1) * sz - mx) / (sz - 1) + 1
        de = pn[u] * (ev[u] - nev)
        dx = max(dx, de)
        
    print(ev[0] - dx)

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int, readline().split())
M = map(int, read().split())
edges = zip(M, M)

edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]

for _from, to in edges:
    edges_from[_from-1].append(to-1)

E_dist_to_goal = [0] * n
P_of_reaching = [0] * n
P_of_reaching[0] = 1

for v in range(n-2, -1, -1):
    routes = edges_from[v]
    for next_v in routes:
        E_dist_to_goal[v] += E_dist_to_goal[next_v] + 1
    E_dist_to_goal[v] /= len(routes)

for v in range(n-1):
    P_now = P_of_reaching[v]
    routes = edges_from[v]
    P_next = P_now / len(routes)
    for next_v in routes:
        P_of_reaching[next_v] += P_next

initial_ans = E_dist_to_goal[0]
cut = 0
for v in range(n-2):
    routes = edges_from[v]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        continue
    not_cut_dist = E_dist_to_goal[v]
    longest_dist = max([E_dist_to_goal[next_v]+1 for next_v in routes])
    after_cut_dist = (not_cut_dist - longest_dist/num_of_routes) * num_of_routes / (num_of_routes-1)
    delta = (not_cut_dist - after_cut_dist) * P_of_reaching[v]
    cut = max(cut, delta)

ans = initial_ans - cut
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
P_of_reaching = [0] * n
P_of_reaching[0] = 1

for v in range(n-2, -1, -1):
    routes = edges_from[v]
    for next_v in routes:
        E_dist_to_goal[v] += E_dist_to_goal[next_v] + 1
    E_dist_to_goal[v] /= len(routes)

for v in range(n-1):
    P_now = P_of_reaching[v]
    routes = edges_from[v]
    P_next = P_now / len(routes)
    for next_v in routes:
        P_of_reaching[next_v] += P_next

initial_ans = E_dist_to_goal[0]
short_cut = 0
for v in range(n-2):
    routes = edges_from[v]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        continue
    not_cut_dist = E_dist_to_goal[v]
    longest_dist = max([E_dist_to_goal[next_v]+1 for next_v in routes])
    after_cut_dist = (not_cut_dist - longest_dist/num_of_routes) * num_of_routes / (num_of_routes-1)
    delta = (not_cut_dist - after_cut_dist) * P_of_reaching[v]
    short_cut = max(short_cut, delta)

ans = initial_ans - short_cut
print(ans)

Solution (Python):
n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
P_of_reaching = [0] * n
P_of_reaching[0] = 1

for v in range(n-2, -1, -1):
    routes = edges_from[v]
    for next_v in routes:
        E_dist_to_goal[v] += E_dist_to_goal[next_v] + 1
    E_dist_to_goal[v] /= len(routes)

for v in range(n-1):
    P_now = P_of_reaching[v]
    routes = edges_from[v]
    P_next = P_now / len(routes)
    for next_v in routes:
        P_of_reaching[next_v] += P_next

initial_ans = E_dist_to_goal[0]
answers = [initial_ans]
for v in range(n-2):
    routes = edges_from[v]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        continue
    not_cut_dist = E_dist_to_goal[v]
    longest_dist = max([E_dist_to_goal[next_v]+1 for next_v in routes])
    after_cut_dist = (not_cut_dist - longest_dist/num_of_routes) * num_of_routes / (num_of_routes-1)
    delta = not_cut_dist - after_cut_dist
    candidate = initial_ans - delta * P_of_reaching[v]
    answers.append(candidate)

print(min(answers))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)

    
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])

    
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])

    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)

    print(ans)
resolve()

Solution (Python):
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, m = rrd()

g1 = [[] for _i in range(605)]
g2 = [[] for _i in range(605)]
e = [0] * 605
for i in range(m):
    x, y = rrd()
    g1[x].append(y)
    g2[y].append(x)

p = [0] * 605
p[1] = 1
for i in range(1, n + 1):
    for j in g1[i]:
        p[j] += p[i]/len(g1[i])

for i in range(n, 0, -1):
    for j in g1[i]:
        e[i] += (e[j] + 1) / len(g1[i])
ans = e[1]

for i in range(n, 0, -1):
    ne = 0
    if len(g1[i]) == 1:
        continue
    for j in g1[i]:
        ne += (e[j] + 1) / (len(g1[i]) - 1)

    for j in g1[i]:
        dis = ne - (e[j] + 1) / (len(g1[i]) - 1) - e[i]
        ans = min(ans,e[1] + p[i]*dis)

print(ans)

Solution (Python):
n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
for node in range(n-2, -1, -1):
    routes = edges_from[node]
    num_of_routes = len(routes)
    for next_node in routes:
        dist = E_dist_to_goal[next_node] + 1
        E_dist_to_goal[node] += dist/num_of_routes


def recalculate_dist(node, E_dist_to_goal):
    recal_E_dist = [0]*(node+1)
    routes = edges_from[node]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        return False

    heaviest_route = max(E_dist_to_goal[next_node]+1 for next_node in routes)
    new_dist = E_dist_to_goal[node] - heaviest_route/num_of_routes
    new_dist *= num_of_routes / (num_of_routes - 1)
    recal_E_dist[node] = new_dist

    for v in range(node-1, -1, -1):
        routes = edges_from[v]
        num_of_routes = len(routes)
        for nv in routes:
            if nv > node:
                dist = E_dist_to_goal[nv] + 1
            else:
                dist = recal_E_dist[nv] + 1
            recal_E_dist[v] += dist
        recal_E_dist[v] /= num_of_routes
    return recal_E_dist[0]


ans = [E_dist_to_goal[0]]
for i in range(n-2):
    candidate = recalculate_dist(i, E_dist_to_goal)
    if candidate:
        ans.append(candidate)

print(min(ans))

Solution (Python):
n,m = map(int,input().split())
g = [list() for _ in range(n)]
for _ in range(m):
  s,t = map(int,input().split())
  g[s-1].append(t-1)
prop = [0]*n
expc = [10**6]*n
prop[0] = 1
expc[-1] = 0
for i in range(n):
  if not g[i]:
    continue
  t = len(g[i])
  for x in g[i]:
    prop[x] += prop[i]/t
for i in range(n-1,-1,-1):
  if not g[i]:
    continue
  t = len(g[i])
  f = 0
  for x in g[i]:
    f += expc[x] + 1.0
  f /= t
  expc[i] = f

cans = expc[0]
for i in range(n-1):
  t = len(g[i])
  if t < 2:
    continue
  c = max(expc[x] for x in g[i])
  ne = (expc[i]*t - (c+1))/(t-1)
  de = expc[i] - ne
  na = expc[0] - de*prop[i]
  if cans > na:
    cans = na
print(cans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)

    
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])

    
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])

    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        
        w=max(*((E[w],w) for w in edges[v]))[1]
        E_dash=0
        for nv in edges[v]:
            if(nv==w): continue
            E_dash+=E[nv]
        E_dash=1+E_dash/(len(edges[v])-1)
        dE=E_dash-E[v]
        ans=min(ans,E[0]+p[v]*dE)

    print(ans)
resolve()

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    n,m=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        Edges[s].append(t)
    DP=[0]*n
    for v in reversed(range(n-1)):
        tmp=0
        for to in Edges[v]:
            tmp+=DP[to]
        DP[v]=tmp/len(Edges[v])+1
    ans=DP[0]
    for v in range(n-1):
        if len(Edges[v])==1:
            continue
        u=max((DP[to],to) for to in Edges[v])[1]
        DP2=[0]*n
        for w in reversed(range(n-1)):
            tmp=0
            for to in Edges[w]:
                if w==v and to==u:
                    continue
                tmp+=DP2[to]
            if w==v:
                DP2[w]=tmp/(len(Edges[w])-1)+1
            else:
                DP2[w]=tmp/len(Edges[w])+1
        ans=min(ans,DP2[0])
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

for _ in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    edges[s].append(t)

def E(stop):
    dp = [-1] * N
    dp[N - 1] = 0
    for i in range(N - 1)[:: -1]:
        total = 0
        maxE = 0
        for to in edges[i]:
            total += dp[to]
            if maxE < dp[to]:
                maxE = dp[to]
        size = len(edges[i])
        if size > 1 and stop == i:
            size -= 1
            total -= maxE
        dp[i] = total / size + 1
    return dp[0]

ans = float('inf')
for s in range(N):
    ans = min(ans, E(s))

print(ans)

Solution (Python):
def solve():
    import sys

    input = sys.stdin.readline

    n, m = map(int, input().split())
    edges = tuple(set() for _ in range(n))

    for _ in range(m):
        s, t = map(int, input().split())
        edges[s - 1].add(t - 1)

    ans = float('inf')
    for del_vertical in range(n):
        E = [0] * n
        
        for v in reversed(range(n - 1)):
            mx = -1
            for u in edges[v]:
                E[v] += E[u]
                if mx < E[u]:
                    mx = E[u]
            if v == del_vertical and len(edges[v]) > 1:
                E[v] = (E[v] - mx) / (len(edges[v]) - 1) + 1
            else:
                E[v] = E[v] / len(edges[v]) + 1
        ans = min(ans, E[0])
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

d.sort()
l = [0] * n
for i in range(m):
    d[i] = [d[i][0]-1, d[i][1]-1]
    l[d[i][0]] += 1

p = [0] * n
p[0] = 1
for x in d:
    p[x[1]] += p[x[0]]/l[x[0]]

e = [0] * n
index = d[-1][0]
max_in_index = 0
max_reduce_e = 0

for x in d[::-1] + [[-1, -1]]:
    if index != x[0]:
        if l[index] > 1:
            max_reduce_e = max(max_reduce_e, 
                               p[index] * (e[index]/l[index] - (e[index] - max_in_index)/(l[index] - 1)))
        e[index] /= l[index]
        index = x[0]
        max_in_index = 0
    max_in_index = max(max_in_index, e[x[1]] + 1)
    e[x[0]] += e[x[1]] + 1

print(e[0] - max_reduce_e)

Solution (Python):
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

d.sort()
l = [0] * n
for i in range(m):
    d[i] = [d[i][0]-1, d[i][1]-1]
    l[d[i][0]] += 1

p = [0] * n
p[0] = 1
for x in d:
    p[x[1]] += p[x[0]]/l[x[0]]

e = [0] * n
index = d[-1][0]
max_in_index = 0
max_reduce_e = 0

for x in d[::-1] + [[-1, -1]]:
    if index != x[0]:
        if l[index] > 1:
            max_reduce_e = max(max_reduce_e, 
                               p[index] * (e[index]/l[index] - (e[index] - max_in_index)/(l[index] - 1)))
        e[index] /= l[index]
        index = x[0]
        max_in_index = 0
    max_in_index = max(max_in_index, e[x[1]] + 1)
    e[x[0]] += e[x[1]] + 1

print(e[0] - max_reduce_e)

Solution (Python):
import sys

n, m = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = map(int, line.split())
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1


expected = [0.] * n


reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = [expected[j] for j in links[i]]
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.


probability = [0.] * n
probability[0] = 1.

for i in range(n - 1):
    jp = probability[i] / counts[i]
    for j in links[i]:
        probability[j] += jp

print(expected[0] - max(p * r for p, r in zip(probability, reducible)))

Solution (Python):
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

d.sort()
for i in range(m):
    d[i] = [d[i][0]-1, d[i][1]-1]

l = [0] * n
for x in d:
    l[x[0]] += 1

p = [0] * n
p[0] = 1
for x in d:
    p[x[1]] += p[x[0]]/l[x[0]]

e = [0] * n
index = d[-1][0]
max_in_index = 0
max_reduce_e = 0

for x in d[::-1] + [[-1, -1]]:
    if index != x[0]:
        if l[index] > 1:
            max_reduce_e = max(max_reduce_e, 
                               p[index] * (e[index]/l[index] - (e[index] - max_in_index)/(l[index] - 1)))
        e[index] /= l[index]
        index = x[0]
        max_in_index = 0
        if index == -1:
            break
    max_in_index = max(max_in_index, e[x[1]] + 1)
    e[x[0]] += e[x[1]] + 1

print(e[0] - max_reduce_e)

Solution (Python):
import sys

n, m = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = map(int, line.split())
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1


expected = [0.] * n
exp_get = expected.__getitem__


reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = list(map(exp_get, links[i]))
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.


probability = [0.] * n
probability[0] = 1.

for i in range(n - 1):
    jp = probability[i] / counts[i]
    for j in links[i]:
        probability[j] += jp

print(expected[0] - max(p * r for p, r in zip(probability, reducible)))

Solution (Python):
import sys

n, m = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = map(int, line.split())
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1


expected = [0.] * n
exp_get = expected.__getitem__


reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = list(map(exp_get, links[i]))
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.


probability = [0.] * n
probability[0] = 1.

rdc = 0.

for i in range(n - 1):
    fp = probability[i]
    jp = fp / counts[i]
    for j in links[i]:
        probability[j] += jp
    rdc = max(rdc, fp * reducible[i])

print(expected[0] - rdc)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
m = map(int,read().split())
ST = zip(m,m)

out_edge = [[] for _ in range(N+1)]
in_edge = [[] for _ in range(N+1)]

for s,t in ST:
    out_edge[s].append(t)
    in_edge[t].append(s)

out_deg = [len(x) for x in out_edge]

arrive_prob = [0]*(N+1)
arrive_prob[1] = 1.0
for n in range(2,N+1):
    arrive_prob[n] = sum(arrive_prob[p]/out_deg[p] for p in in_edge[n])








expected_from = [0]*(N+1)
for n in range(N-1,0,-1):
    expected_from[n] = 1+sum(expected_from[c] for c in out_edge[n])/out_deg[n]

current_time = expected_from[1]

improve = 0
for n in range(1,N):
    if out_deg[n] == 1:
        continue
    x = expected_from[n]
    d = out_deg[n]
    y = (d*(x-1)-max(expected_from[c] for c in out_edge[n]))/(d-1) + 1
    value = (x-y)*arrive_prob[n]
    if improve < value:
        improve = value

answer = current_time - improve
print(answer)