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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    s, t = LI()
    G[s - 1] += [t - 1]

route_len = [0] * n
for u in range(n - 2, -1, -1):
    route_len[u] = sum([route_len[v] + 1 for v in G[u]]) / len(G[u])


prob = [0] * n
prob[0] = 1
for u in range(n - 1):
    for v in G[u]:
        prob[v] += prob[u] / len(G[u])


ans = route_len[0]
for u in range(n - 1):
    if len(G[u]) == 1:
        continue
    new_route_len = (sum([route_len[v] + 1 for v in G[u]]) - max([route_len[v] + 1 for v in G[u]])) / (len(G[u]) - 1)
    ans = min(ans, route_len[0] - prob[u] * (route_len[u] - new_route_len))



print(ans)

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)

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

    g = [[] for _ in range(n)]

    for s, t in st:
        s -= 1
        t -= 1
        g[s].append(t)

    deg = [len(x) for x in g]

    dp = [0] * n

    for u in range(n-1)[::-1]:
        now = 0
        for v in g[u]:
            now += dp[v]

        now /= deg[u]
        now += 1
        dp[u] = now

    ans = dp[0]

    for u in range(n-1):
        if deg[u] == 1:
            continue

        d = g[u][0]
        for v in g[u]:
            if dp[d] < dp[v]:
                d = v

        dp2 = [0] * n
        for x in range(n - 1)[::-1]:
            now = 0
            for y in g[x]:
                if x == u and y == d:
                    continue
                now += dp2[y]

            if x == u:
                now /= deg[x] - 1
            else:
                now /= deg[x]

            now += 1
            dp2[x] = now

        ans = min(ans, dp2[0])

    print(ans)


if __name__ == "__main__":
    main()

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

g = [[] for _ in range(N+1)]
ig = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    ig[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp3 = [0] * (N+1)
dp1[1] = 1

for i in range(1, N+1):
    for j in ig[i]:
        dp1[i] += dp1[j]/len(g[j])
df = 0
for i in range(N, 0, -1):
    for v in g[i]:
        dp2[i] += (dp2[v]+1)/len(g[i])
        if len(g[i]) != 1:
            dp3[i] += (dp2[v]+1)/(len(g[i])-1)
    for v in g[i]:
        if len(g[i]) != 1:
            pv = dp3[i] - (dp2[v]+1)/(len(g[i])-1)
            df = max(df, dp1[i]*(dp2[i]-pv))
print(dp2[1]-df)

Solution (Python):
import copy
N,M=map(int,input().split())
linked=[set() for i in range(N)]
for i in range(M):
  s,t=map(int,input().split())
  linked[s-1].add(t-1)
def dp(link):
  dp=[0]*N
  for i in range(N-1):
    k=N-2-i
    size=len(link[k])
    if size==0:
      continue
    p=1/size
    v=0
    for t in link[k]:
      v=v+p*(dp[t]+1)
    dp[k]=v
  return dp
all_dp=dp(linked)
ans=all_dp[0]
for i in range(N-1):
  if len(linked[i])<2:
    continue
  cut=0
  v=0
  for t in linked[i]:
    if v<all_dp[t]:
      cut=t
      v=all_dp[t]
  linked[i].remove(cut)
  d=dp(linked)
  ans=min(ans,d[0])
  linked[i].add(cut)
print(ans)

Solution (Python):


n,m = map(int, input().split( ))

E= [[] for _ in range(n)]

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

dp = [0]*n 

for s in range(n-2,-1,-1):
    for t in E[s]:
        dp[s] += dp[t]
    if E[s]:
        dp[s] /= len(E[s])
    dp[s] += 1



ans = dp[0]
for s2 in range(n-1):
    if len(E[s2])-1:
        dp2 = [0]*n
        mxi = 0
        mxt = -1
        for t in E[s2]:
            if mxt<dp[t]:
                mxi = t 
                mxt = dp[t]
        if mxt<0:
            continue            
        for s in range(n-2,-1,-1):
            for t in E[s]:
                dp2[s] += dp2[t]
            if s ==s2:
                dp2[s] -= mxt
            if s == s2:
                dp2[s] /= (len(E[s])-1)
            elif E[s]:
                dp2[s] /= len(E[s])
            dp2[s] += 1
        ans = min(ans, dp2[0])
        

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)
    for _ in range(m):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        to[s].append(t)
    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
    ans = ev[0]
    for nu in range(n - 1):
        if len(to[nu]) == 1: continue
        mx = 0
        mv = 0
        for nv in to[nu]:
            if ev[nv] > mx:
                mx = ev[nv]
                mv = nv
        for u in range(nu, -1, -1):
            s = 0
            for ku in to[u]:
                if (u, ku) == (nu, mv): continue
                s += ev[ku]
            od = len(to[u])
            if u == nu: od -= 1
            ev[u] = s / od + 1
        ans = min(ans, ev[0])
    print(ans)

main()

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())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        for nv in E[v]:
            dp[v]+=dp[nv]
        dp[v]/=len(E[v])
        dp[v]+=1
    ans=dp[0]

    
    for u in range(n):
        if(len(E[u])<=1): continue
        nu=max(*((dp[nu],nu) for nu in E[u]))[1]
        dp2=[0]*n
        for v in range(n-2,-1,-1):
            for nv in E[v]:
                if(v==u and nv==nu): continue
                dp2[v]+=dp2[nv]
            dp2[v]/=(len(E[v]) if v!=u else len(E[v])-1)
            dp2[v]+=1
        ans=min(ans,dp2[0])
    print(ans)
resolve()

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())
    E=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1;
        E[s].append(t)
    dp=[0]*n
    for v in range(n-2,-1,-1):
        res=0
        for nv in E[v]: res+=dp[nv]
        dp[v]=1+res/len(E[v])
    ans=dp[0] 

    
    for v in range(n-1):
        if(len(E[v])==1): continue
        u=max(*((dp[nv],nv) for nv in E[v]))[1]
        
        dp2=[0]*n
        for x in range(n-2,-1,-1):
            res=0
            for nx in E[x]:
                if(x==v and nx==u): continue
                res+=dp2[nx]
            if(v!=x):
                dp2[x]=1+res/len(E[x])
            else:
                dp2[x]=1+res/(len(E[x])-1)
        ans=min(ans,dp2[0])
    print(ans)
resolve()

Solution (Python):
import sys
import copy

input = sys.stdin.readline

N, M = list(map(int,input().split()))
st = [list(map(int,input().split())) for i in range(M)]

neighbor = [[] for i in range(N)]
for s,t in st:
	neighbor[s-1].append(t-1)

INF = 100100100
ev = [INF]*N
ev[N-1] = 0
for i in range(N-2,-1,-1):
	dsum = 0
	dcount = 0
	for j in neighbor[i]:
		dsum += ev[j]
		dcount += 1
	ev[i] = dsum/dcount + 1

prb = [0]*N
prb[0] = 1
for i in range(N-1):
	for j in neighbor[i]:
		prb[j] += prb[i]/len(neighbor[i])

ans = ev[0]
for s, t in st:
	ss, tt = s-1, t-1
	pnum = len(neighbor[ss])
	if pnum==1: continue
	evdif = (ev[ss]-(ev[ss]*pnum-(ev[tt]+1))/(pnum-1))*prb[ss]
	ans = min(ans,ev[0]-evdif)

print(ans)

Solution (Python):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Solution (Python):
import sys
import copy

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().split()))
	st = [list(map(int,input().split())) for i in range(M)]

	neighbor = [[] for i in range(N)]
	for s,t in st:
		neighbor[s-1].append(t-1)

	INF = 100100100
	ev = [INF]*N
	ev[N-1] = 0
	for i in range(N-2,-1,-1):
		dsum = 0
		dcount = 0
		for j in neighbor[i]:
			dsum += ev[j]
			dcount += 1
		ev[i] = dsum/dcount + 1

	ans = ev[0]
	for i in range(N-1):
		evmax = -1
		if len(neighbor[i])==1: continue
		for j in neighbor[i]:
			if ev[j]>evmax:
				tn = j
				evmax = ev[j]

		
		
		evtmp = [INF]*N
		evtmp[i+1::] = ev[i+1::]
		for ii in range(i,-1,-1):
			dsum = 0
			dcount = 0
			for jj in neighbor[ii]:
				if ii==i and jj==tn: continue
				dsum += evtmp[jj]
				dcount += 1
			evtmp[ii] = dsum/dcount + 1

		if evtmp[0]<ans:
			ans = evtmp[0]

	print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)

def dfs(pos):
    if dp[pos] != -1:
        return dp[pos]
    p = len(graph[pos])
    dp[pos] = 0
    if p == 0:
        return dp[pos]
    for next_pos in graph[pos]:
        dp[pos] += dfs(next_pos) / p
    dp[pos] += 1
    return dp[pos]

dp = [-1]*n
dfs(0)
ans = dp[0]

def dfs_1(pos):
    if dq[pos] != -1:
        return dq[pos]
    p = len(graph[pos])
    if pos == i:
        p -= 1
    dq[pos] = 0
    if p == 0:
        return dq[pos]
    for next_pos in graph[pos]:
        if pos == i and next_pos == ind:
            continue
        dq[pos] += dfs_1(next_pos) / p
    dq[pos] += 1
    return dq[pos]

for i in range(n):
    num = 0
    ind = 0
    if len(graph[i]) <= 1:
        continue
    for j in graph[i]:
        if num < dp[j]:
            num = dp[j]
            ind = j
    dq = [-1]*n
    dfs_1(0)
    ans = min(dq[0], ans)
print(ans)

Solution (Python):

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

lis = [[] for i in range(N)]
rlis = [[] for i in range(N)]
mlis = [0] * N

for i in range(M):

    s,t = map(int,input().split())
    s -= 1
    t -= 1

    lis[s].append(t)
    rlis[t].append(s)


odp = [0] * N

for i in range(N):

    i = N - 1 - i

    for j in lis[i]:

        odp[i] += (odp[j] + 1)/len(lis[i])
        

ans = odp[0]


for k in range(N):

    dp = [0] * N
    flag = True

    for i in range(N):

        i = N - 1 - i

        if i != k:

            if k < i:
                dp[i] = odp[i]

            else:

                for j in lis[i]:

                    dp[i] += (dp[j] + 1)/len(lis[i])

        else:

            maxi = 0

            for j in lis[i]:

                maxi = max(maxi,dp[j])
                dp[i] += (dp[j] + 1)

            if len(lis[i]) > 1:
                dp[i] = (dp[i]-(maxi+1)) / (len(lis[i])-1)

            else:
                flag = False
                
    

    if flag:
        ans = min(ans,dp[0])

print (ans)

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

not_omitted = [0.0] * n
exp_get = not_omitted.__getitem__
for j in range(n - 2, -1, -1):
    not_omitted[j] = sum(map(exp_get, links[j])) / counts[j] + 1

ans = 1e6

for i in range(n - 1):
    expected = [0.0] * n
    expected[i + 1:] = not_omitted[i + 1:]
    e_get = expected.__getitem__

    if counts[i] == 1:
        expected[i] = sum(map(e_get, links[i])) / counts[i] + 1
    else:
        exp = list(map(e_get, links[i]))
        expected[i] = (sum(exp) - max(exp)) / (counts[i] - 1) + 1

    for j in range(i - 1, -1, -1):
        expected[j] = sum(map(e_get, links[j])) / counts[j] + 1

    ans = min(ans, expected[0])

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    v_ = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v_[b].append(a)
    dp = [0]*n
    for y in range(1,n)[::-1]:
        d = dp[y]
        for x in v_[y]:
            dp[x] += (d+1)/len(v[x])
    ans = dp[0]
    p = [0]*n
    p[0] = 1
    for x in range(n-1):
        d = p[x]/len(v[x])
        for y in v[x]:
            p[y] += d
    for a in range(n-1):
        if len(v[a]) == 1:
            continue
        m = max([dp[b] for b in v[a]])
        for b in v[a]:
            if dp[b] == m:
                break
        l = dp[0]
        k = dp[a]
        dp[a] = 0
        le = len(v[a])-1
        for y in v[a]:
            if y == b:
                continue
            dp[a] += (dp[y]+1)/le
        d = l+p[a]*(dp[a]-k)
        dp[0] = l
        if 0 < d < ans:
            ans = d
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    v_ = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v_[b].append(a)
    dp = [0]*n
    for y in range(1,n)[::-1]:
        v_[y].sort()
        d = dp[y]
        for x in v_[y]:
            dp[x] += (d+1)/len(v[x])
    ans = dp[0]
    p = [0]*n
    p[0] = 1
    for x in range(n-1):
        d = p[x]/len(v[x])
        for y in v[x]:
            p[y] += d
    for a in range(n-1):
        if len(v[a]) == 1:
            continue
        m = max([dp[b] for b in v[a]])
        for b in v[a]:
            if dp[b] == m:
                break
        l = dp[0]
        k = dp[a]
        dp[a] = 0
        le = len(v[a])-1
        for y in v[a]:
            if y == b:
                continue
            dp[a] += (dp[y]+1)/le
        d = l+p[a]*(dp[a]-k)
        dp[0] = l
        if 0 < d < ans:
            ans = d
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    v_ = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v_[b].append(a)
    dp = [0]*n
    for y in range(1,n)[::-1]:
        v_[y].sort()
        d = dp[y]
        for x in v_[y]:
            dp[x] += (d+1)/len(v[x])
    ans = dp[0]
    lx = []
    for a in range(n-1):
        lx.append(len(v[a])-1)
        if len(v[a]) == 1:
            lx[-1] += 1
            continue
        m = max([dp[b] for b in v[a]])
        for b in v[a]:
            if dp[b] == m:
                break
        for i in range(a+1):
            dp[i] = 0
        for y in range(1,n)[::-1]:
            d = dp[y]
            for x in v_[y]:
                if x > a:
                    break
                if (x,y) == (a,b):
                    continue
                dp[x] += (d+1)/lx[x]
        if 0 < dp[0] < ans:
            ans = dp[0]
        lx[-1] += 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    v_ = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v_[b].append(a)
    dp_ = [0]*n
    for y in range(1,n)[::-1]:
        v_[y].sort()
        d = dp_[y]
        for x in v_[y]:
            dp_[x] += (d+1)/len(v[x])
    ans = dp_[0]
    lx = []
    for a in range(n-1):
        lx.append(len(v[a])-1)
        if len(v[a]) == 1:
            lx[-1] += 1
            continue
        m = max([dp_[b] for b in v[a]])
        for b in v[a]:
            if dp_[b] == m:
                break
        for i in range(a+1):
            dp_[i] = 0
        for y in range(1,n)[::-1]:
            d = dp_[y]
            for x in v_[y]:
                if x > a:
                    break
                if (x,y) == (a,b):
                    continue
                dp_[x] += (d+1)/lx[x]
        if 0 < dp_[0] < ans:
            ans = dp_[0]
        lx[-1] += 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

N,M=map(int,input().split())
R=[tuple(map(int,input().split())) for i in range(M)]

E=[set() for i in range(N)]

for x,y in R:
    E[x-1].add(y-1)

DP=[M]*N
DP[N-1]=0

for i in range(N-2,-1,-1):
    score=0
    for x in E[i]:
        score+=1+DP[x]

    DP[i]=score/len(E[i])
        
ANS=DP[0]

for i in range(N-2):
    rem=-1
    remsc=0
    for j in E[i]:
        if DP[j]>remsc:
            rem=j
            remsc=DP[j]

    if remsc==0:
        continue

    E[i].remove(rem)

    NDP=[M]*N
    NDP[N-1]=0

    for l in range(N-2,-1,-1):
        
        score=0
        
        if len(E[l])==0:
            continue
        
        for x in E[l]:
            score+=1+NDP[x]

        NDP[l]=score/len(E[l])

    

    ANS=min(ANS,NDP[0])
    E[i].add(rem)

print(ANS)

Solution (Python):

import sys
from collections import Counter
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append(t)


def solve(N: int, M: int, s: "List[int]", t: "List[int]"):
    c = Counter(s)
    g = Graph(N)
    for ss, tt in zip(s, t):
        g.add_edge(ss, tt)

    DP = [0]*N
    for i in range(N-2, -1, -1):
        DP[i] = sum(DP[t] for t in g.E[i])/c[i] + 1

    gm = DP[0]
    for i in range(N-2):
        if len(g.E[i]) == 1:
            continue
        dp = DP[:]
        for j in range(i, -1, -1):
            tot, m = 0, 0
            for t in g.E[j]:
                tot += dp[t]
                m = max(dp[t], m)
            if i == j:
                dp[j] = (tot-m)/(c[j]-1)
            else:
                dp[j] = tot/c[j]
            dp[j] += 1
        gm = min(dp[0], gm)
        
    print(gm)


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    s = [int()] * (M)  
    t = [int()] * (M)  
    for i in range(M):
        s[i] = int(next(tokens))-1
        t[i] = int(next(tokens))-1
    solve(N, M, s, t)


if __name__ == '__main__':
    main()

Solution (Python):
import math

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for _ in range(M)]

forward_edges = {n+1:[] for n in range(N)}
reverse_edges = {n+1:[] for n in range(N)}
for e in edges:
  forward_edges[e[0]].append(e[1])
  reverse_edges[e[1]].append(e[0])


estimated_distance = {n+1:None for n in range(N)}
estimated_distance[N] = 0
probability = {n+1:None for n in range(N)}
probability[1] = 1
def get_probability(n):
  if probability[n] is not None:
    return probability[n]
  prob = 0
  for m in reverse_edges[n]:
    prob += get_probability(m) / len(forward_edges[m])
  probability[n] = prob
  return prob
  
def get_distance(n):
  if estimated_distance[n] is not None:
    return estimated_distance[n]
  total_distance = 0
  for m in forward_edges[n]:
    total_distance += get_distance(m)
  estimated_distance[n] = 1 + total_distance / len(forward_edges[n])
  return estimated_distance[n]


before_distance = get_distance(1)
max_decrease = 0
for n in range(1, N):
  if len(forward_edges[n]) == 1:
    continue
  distances = [get_distance(m) for m in forward_edges[n]]
  distance_diff = sum(distances) / len(distances) - (
    sum(distances)-max(distances))/(len(distances)-1)
  decrease = get_probability(n) * distance_diff
  max_decrease = max(max_decrease, decrease)

print(before_distance - max_decrease)

Solution (Python):
N, M = map(int, input().split())
ST = [list(map(int, input().split())) for _ in range(M)]
ST.sort()
Edge_out = [[] for _ in range(N+1)]
Edge_in = [[] for _ in range(N+1)]
for s, t in ST:
    Edge_out[s].append(t)
    Edge_in[t].append(s)

P_node = [0] * (N+1)  
P_edge = [0] * (N+1)  
P_node[1] = 1
for v, edge_out in enumerate(Edge_out[1:-1], 1):
    deg = len(edge_out)
    p = P_node[v] / deg
    P_edge[v] = p
    for u in edge_out:
        P_node[u] += p














E_node_out = [0] * (N+1)  

for v in range(N-1, 0, -1):
    edge_out = Edge_out[v]
    su = 0
    for u in edge_out:
        su += E_node_out[u]
    su /= len(edge_out)
    su += 1
    E_node_out[v] = su











ans = 0
for s, t in ST:
    p_s = P_node[s]
    
    deg = len(Edge_out[s])
    if deg==1:
        continue
    e = (E_node_out[s] - (1+E_node_out[t]) / deg) * (deg / (deg - 1))
    a = p_s * (e - E_node_out[s])
    
    ans = min(ans, a)
print(ans + E_node_out[1])

Solution (Python):



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


n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for _ in range(m):
    s,t = [int(i)-1 for i in readline().split()]
    g[s].append(t)

L = [len(gi) for gi in g]

p = [0]*n
p[0] = 1
for i in range(n-1):
    c = p[i]/L[i]
    for v in g[i]:
        p[v] += c

dp0 = [0]*(n)
dp1 = [1000000]*(n)

for i in range(n-2,-1,-1):
    res = 0
    m = 0
    for v in g[i]:
        res += dp0[v]
        if m<dp0[v]: m = dp0[v]
    dp0[i] = 1 + res/L[i]

    if L[i] >= 2:
        dp1[i] = 1 + (res-m)/(L[i]-1)
    
res = max((dp0[i] - dp1[i])*p[i] for i in range(n))

print(dp0[0]-max(0,res))

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

dp = [0]*N
for i in range(N-2,-1,-1):
    dp[i] = 0
    for j in l[i]:
        dp[i] += dp[j]
    dp[i] /= len(l[i])
    dp[i] += 1

ans = dp[0]
for s in range(N-1):
    if len(l[s])==1:
        continue
    M = 0
    t = 0
    for j in l[s]:
        if M < dp[j]:
            M = dp[j]
            t = j
    dp_ = [0]*N
    for i in range(N-2,-1,-1):
        dp_[i] = 0
        for j in l[i]:
            if i != s or j != t:
                dp_[i] += dp_[j]
        if i != s:
            dp_[i] /= len(l[i])
        else:
            dp_[i] /= len(l[i])-1
        dp_[i] += 1
    ans = min(ans,dp_[0])
print(ans)

Solution (Python):
N, M = map(int, input().split())
E = [set() for i in range(N)]
for i in range(M):
  s, t = map(int, input().split())
  s, t = s-1, t-1
  E[s].add(t)
Vs = [1000000.0]*N
Vs[-1] = 0
for i in reversed(range(N-1)):
  js = E[i]
  v = 0
  for j in js:
    v += Vs[j]
  v = 1+v/len(js)
  Vs[i] = v
r = Vs[0]
rs = [r]
Vs0 = Vs
for n in range(N-1):
  Vs = [1000000.0]*N
  for i in range(n+1, N):
    Vs[i] = Vs0[i]
  for i in reversed(range(n+1)):
    js = E[i]
    if i == n:
      jmin = max(js, key=lambda j: Vs[j])
      js = js-{jmin}
    if len(js) == 0:
      break
    
    v = 0
    for j in js:
      v += Vs[j]
    v = 1+v/len(js)
    Vs[i] = v
  r = Vs[0]
  rs.append(r)

r = min(rs)
print(r)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    deg2 = [0]*n
    atode = []
    for i in range(m):
        s, t = map(int, input().split())
        g[s-1].append(t-1)
        deg2[s-1] += 1
        atode.append((s-1,t-1))

    ee = [-1]*n
    def rec2(cur, s,t):
        if ee[cur] != -1:
            return ee[cur]
        res = 0
        cnt = 0
        for to in g[cur]:
            if cur==s and to ==t:
                continue
            res += rec2(to,s,t)+1
            cnt += 1
        if cnt:
            res /= cnt
        ee[cur] = res
        return ee[cur]

    rec2(0,-1,-1)
    ret = ee[0]

    use = [[-1, -1] for i in range(n)]
    for s,t in atode:
        if deg2[s] < 2:
            continue
        if use[s][1] < ee[t]:
            use[s][0] = t
            use[s][1] = ee[t]

    for s, (t,cost) in enumerate(use):
        if s == -1:
            continue
        ee = [-1]*n
        rec2(0,s,t)
        ret = min(ret, ee[0])
    print(ret)

if __name__ == "__main__":
    main()