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 sys
input = sys.stdin.readline


N,M = map(int,input().split())
ST = [list(map(int,input().split())) for _ in [0]*M]

Ef = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]

for s,t in ST:
    s -= 1
    t -= 1
    Ef[s].append(t)
    Eb[t].append(s)

V = [0]*N
for i in range(N-2,-1,-1):
    tmp_sum = 0
    tmp_num = 0
    for j in Ef[i]:
        tmp_num += 1
        tmp_sum += V[j]
    V[i] = tmp_sum/tmp_num + 1.0

bq = []
for bi in range(i,N-1):
    if len(Ef[bi]) <= 1:
        continue
    bj = 0
    tmp = 0
    for j in Ef[bi]:
        if tmp<V[j]:
            tmp = V[j]
            bj = j
    bq.append((bi,bj))

ans = V[0]
for bi,bj in bq:
    V2 = [0]*N
    for i in range(N-2,-1,-1):
        tmp_sum = 0
        tmp_num = 0
        for j in Ef[i]:
            if i==bi and j==bj : continue
            tmp_num += 1
            tmp_sum += V2[j]
        V2[i] = tmp_sum/tmp_num + 1.0
    ans = min(ans,V2[0])
print(ans)

Solution (Python):

import sys
import math
from collections import deque
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = 10**15


n, m = [int(item) for item in input().split()]
possibility = [0] * n
possibility[0] = 1.0

class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                if len(self.adj[v]):
                    p = possibility[v] / len(self.adj[v])
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    possibility[dest] += p
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v.extend(to_be_added)
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

edge = [[] for _ in range(n)]
for i in range(m):
    s, t = [int(item) - 1 for item in input().split()]
    edge[s].append(t)
dag = DirectedGraph(edge)
tps = dag.topological_sort()
distance = [0] * n
mdist = []

for item in tps[::-1]:
    if item == n-1:
        continue
    dist = 0.0
    max_dist = 0.0
    for dest in edge[item]:
        dist += distance[dest] + 1  
        max_dist = max(max_dist, distance[dest] + 1)
    distance[item] = dist / len(edge[item])
    if len(edge[item]) > 1:
        diff = distance[item] - (dist - max_dist) / (len(edge[item]) - 1)
        mdist.append((diff * possibility[item], item))
mdist.sort(reverse=True)
if len(mdist) > 0:
    print(distance[0] - mdist[0][0])
else:
    print(distance[0])

Solution (Python):
import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(100000)
import heapq
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def solve():
    return

def hakai(cur_tubusi, rooms, revrooms, ex, n):
    if len(rooms[cur_tubusi]) == 0:
        return 1000000
    elif len(rooms[cur_tubusi]) == 1:
        return 1000000
    else:
        ccost = -1
        for cand_tubusi in rooms[cur_tubusi]:
            tmp = ex[cand_tubusi]
            if tmp > ccost:
                ccost = tmp
                tubusi_index = cand_tubusi
        
        
        revrooms[tubusi_index].remove(cur_tubusi)

        ex2 = [0 for i in range(n)]
        npaths2 = [0 for i in range(n)]

        
        

        for i in range(n):
            roomnum = n - i - 1
            
            pcost = ex2[roomnum] + 1
            for par in revrooms[roomnum]:
                ex2[par] = (ex2[par] * npaths2[par] + pcost) / (npaths2[par] + 1)
                npaths2[par] += 1
                
        

        revrooms[tubusi_index].append(cur_tubusi)
        return ex2[0]


def main():
    n,m = getList()
    rooms = [[] for i in range(n + 1)]
    revrooms = [[] for i in range(n + 1)]
    npaths = [0 for i in range(n)]
    for i in range(m):
        a, b = getList()
        revrooms[b-1].append(a-1)
        rooms[a-1].append(b-1)
    ex = [0 for i in range(n)]

    
    

    for i in range(n):
        roomnum = n - i - 1
        
        pcost = ex[roomnum] + 1
        for par in revrooms[roomnum]:
            ex[par] = (ex[par] * npaths[par] + pcost) / (npaths[par] + 1)
            npaths[par] += 1
            
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    ans = ex[0]
    for i in range(n):
        tsekai = hakai(i, rooms, revrooms, ex, n)
        if tsekai < ans:
            ans = tsekai

        

    print(ans)

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):
def solve_f(n, g):
    e_base = [0.0] * (n + 1)
    p_base = [0.0] * (n + 1)

    
    for i in range(n - 1, 0, -1):
        e_base[i] = sum([e_base[j] for j in g[i]]) / len(g[i]) + 1.0

    
    p_base[1] = 1.0
    for i in range(1, n):
        for j in g[i]:
            p_base[j] += p_base[i] / len(g[i])

    

    
    gap = 0.0
    for i in range(1, n):
        if len(g[i]) == 1:
            continue
        total = sum([e_base[j] + 1 for j in g[i]])
        maxim = max([e_base[j] + 1 for j in g[i]])
        gap_i = (total / len(g[i]) - (total - maxim) / (len(g[i]) - 1)) * p_base[i]
        gap = max(gap_i, gap)

    return e_base[1] - gap


def main():
    
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        s, t = map(int, input().split())
        g[s].append(t)
    res = solve_f(n, g)
    print(res)


def test():
    assert abs(solve_f(4, [[], [2, 3, 4], [3, 4], [4]]) - 1.5) < 0.000001
    assert abs(solve_f(3, [[], [2], [3]]) - 2.0) < 0.000001


if __name__ == "__main__":
    test()
    main()

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter


import sys
def input():
	return sys.stdin.readline().strip()

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

graph = [[] for _ in range(N)]

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

base_dist = [-1]*N
base_dist[-1] = 0


for i in range(N - 2, -1, -1):
	total = 0
	for node in graph[i]:
		total += base_dist[node]
	base_dist[i] = total/len(graph[i]) + 1


ans = base_dist[0]
for stop in range(0, N - 1):
	dist = copy.deepcopy(base_dist)
	total = 0
	if len(graph[stop]) == 1:
		continue
	max_d = 0
	for node in graph[stop]:
		max_d = max(max_d, dist[node])
		total += dist[node]
	total -= max_d
	total /= (len(graph[stop]) - 1)
	total += 1
	dist[stop] = total

	for i in range(stop - 1, -1, -1):
		total = 0
		for node in graph[i]:
			total += dist[node]
		dist[i] = total / len(graph[i]) + 1

	ans = min(ans, dist[0])
	

print(ans)

Solution (Python):

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: 
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)

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


inf = 1000000

dp0 = [0]*(n)
dp1 = [inf]*(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 = 0
for i in range(n):
    res = max(res,(dp0[i] - dp1[i])*p[i])

print(dp0[0]-res)

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

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

E = [-1] * N
E[-1] = 0
for i in range(N-1)[::-1]:
    a = 0
    for c in X[i]:
        a += E[c] + 1
    E[i] = a/len(X[i])

P = [0] * N
P[0] = 1

for i in range(1, N):
    for p in Y[i]:
        P[i] += P[p]/len(X[p])

ma = 0
for s, t in Z:
    k = len(X[s])
    if k == 1: continue
    a, b = E[s], E[t]
    c = k/(k-1)*(a-1-b/k)
    ma = max(ma, (a-c-1)*P[s])

print(E[0]-ma)

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    G[s-1].append(t-1)
E = [0]*N
for v in range(N-1)[::-1]:
    n = len(G[v])
    for nv in G[v]:
        E[v]+=(E[nv]+1)*(1/n)
ans = E[0]
for v in range(N-1):
    if len(G[v]) == 1:
        continue
    index = -1
    tmp = -1
    for i, nv in enumerate(G[v]):
        if tmp<E[nv]:
            index = nv
            tmp = E[nv]
    n = len(G[v])-1
    E[v] = 0
    for nv in G[v]:
        if nv == index:
            continue
        E[v]+=(E[nv]+1)*(1/n)
    for vv in range(v)[::-1]:
        E[vv] = 0
        n = len(G[vv])
        for nv in G[vv]:
            E[vv]+=(E[nv]+1)*(1/n)
    ans = min(ans, E[0])
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]

achieve_prob = [0]*(N+1)
achieve_prob[1] = 1.0
for n in range(2,N+1):
    achieve_prob[n] = sum(achieve_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)*achieve_prob[n]
    if improve < value:
        improve = value

answer = current_time - improve
print(answer)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

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

es = [0] * n
for i in range(n-2,-1,-1):
    s = 0
    for e in g[i]:
        s += es[e]
    s = s / len(g[i]) + 1
    es[i] = s



cont = [0] * n
for i in range(n):
    ees = [0] * (i+1)
    ees[-1] = 1.0
    for j in range(i-1,-1,-1):
        t = 0
        for e in g[j]:
            if e <= i:
                t += ees[e]
        ees[j] = t / len(g[j])
    cont[i] = ees[0]


ans = es[0]
for i in range(n):
    if len(g[i]) == 1:
        continue
    s = 0
    for e in g[i]:
        s += es[e]
    minto = es[i]
    for e in g[i]:
        to = (s - es[e])/(len(g[i])-1) + 1
        minto = min(minto, to)
    ans = min(ans, es[0] - (es[i]-minto)*cont[i])
print("{:.14f}\n".format(ans))