Buggy python submission (verdict: Time Limit Exceeded):
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    for w in posts:     # cut: edge from v to w
        outgoing_degree = len(outgoing[v])
        if outgoing_degree <= 1:
            continue
        diff_remain_edge_p = 1/(outgoing_degree*(outgoing_degree-1))
        diff_cut_edge_p = 1/outgoing_degree
        diff_v_ex = sum(diff_remain_edge_p * ex_dp[post] for post in outgoing[v] if post!=w) - diff_cut_edge_p * ex_dp[w]
        min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)


Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Time Limit Exceeded):
def openinput():
    n, m = map(int, input().split())
    edges = [[] for _ in range(m)]
    for _ in range(m):
        si, ti = map(int, input().split())
        edges[si-1].append(ti-1)
    return n, m, edges

def to_n_expected(edges, num_of_nodes, recursive_depth=0):
    dp_table = [0]*num_of_nodes

    recursive_shotest = float('inf')
    for v in reversed(range(n-1)):
        if recursive_depth < 1:
            max_next = max(edges[v], key= lambda x: dp_table[x])
            edges[v].remove(max_next)
            expected = to_n_expected(edges, num_of_nodes, recursive_depth=1)
            edges[v].append(max_next)
            recursive_shotest = min(expected, recursive_shotest)
        
        num_of_nexts = len(edges[v])
        if num_of_nexts > 0:
            dp_table[v] = 1 + sum(dp_table[ne] for ne in edges[v]) / num_of_nexts
        else:
            dp_table[v] = float('inf')
    return min(dp_table[0], recursive_shotest)

if __name__ == '__main__':
    n, m, edges = openinput()
    expcted_values = to_n_expected(edges, n)
    print(expcted_values)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse import csr_matrix

def openinput() :
    n, m = map(int, input().split())
    edges = [[] for _ in range(m)]
    for _ in range(m):
        si, ti = map(int, input().split())
        edges[si-1].append(ti-1)
    return n, m, edges

def to_n_expected(edges, num_of_nodes, recursive_depth=0):
    dp_table = np.zeros(num_of_nodes)
    recursive_shotest = np.inf
    for v in reversed(range(n-1)):
        if recursive_depth < 1:
            max_next = max(edges[v], key= lambda x: dp_table[x])
            edges[v].remove(max_next)
            expected = to_n_expected(edges, num_of_nodes, recursive_depth=1)
            edges[v].append(max_next)
            recursive_shotest = min(recursive_shotest, expected)
        
        out_degree = len(edges[v])
        if out_degree > 0:
            dp_table[v] = 1 + sum(dp_table[ne] for ne in edges[v]) / out_degree
        else:
            dp_table[v] = np.inf
    return min(recursive_shotest, dp_table[0])

if __name__ == '__main__':
    n, m, edges = openinput()
    expcted_values = to_n_expected(edges, n)    # O(nm)
    print(expcted_values)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput() :
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def next_nodes(adjacency_matrix, node):
    return [v for (v, e) in enumerate(adjacency_matrix[node]) if e > 0]


def to_n_expected(adjacency_matrix, num_of_nodes, recursive_depth=0):
    dp_table = np.zeros(num_of_nodes)

    recursive_expected = []
    for v in range(num_of_nodes-1, 0, -1):
        nexts = next_nodes(adjacency_matrix, v-1)
        if recursive_depth < 1:
            max_next = nexts[np.argmax(dp_table[next] for next in nexts)]
            adjacency_matrix[v-1, max_next] = 0
            expected = to_n_expected(adjacency_matrix, num_of_nodes, recursive_depth=1)
            adjacency_matrix[v-1, max_next] = 1
            recursive_expected.append(expected)
        
        num_of_nexts = len(nexts)
        if num_of_nexts > 0:
            dp_table[v-1] = 1 + sum(dp_table[next] for next in nexts) / num_of_nexts
        else:
            dp_table[v-1] = np.inf
    recursive_expected.append(dp_table[0])
    return min(recursive_expected)

if __name__ == '__main__':
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)
    expcted_values = to_n_expected(adjacency_matrix, n)
    print(expcted_values)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput() :
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def next_nodes(adjacency_matrix, node):
    return [v for (v, e) in enumerate(adjacency_matrix[node]) if e > 0]

def editted_mat(mat, weight, edge_from, edge_to):
    copied = copy.deepcopy(mat)
    copied[edge_from, edge_to] = weight
    return copied

def v_to_n_expected(adjacency_matrix, num_of_nodes, recursive_depth=0):
    dp_table = np.zeros(num_of_nodes)

    recursive_expected = []
    for v in range(num_of_nodes-1, 0, -1):
        nexts = next_nodes(adjacency_matrix, v-1)
        if recursive_depth < 1:
            max_next = nexts[np.argmax(dp_table[next] for next in nexts)]
            edimat = editted_mat(adjacency_matrix, 0, v-1, max_next)
            expected = v_to_n_expected(edimat, num_of_nodes, recursive_depth=1)
            recursive_expected.append(expected)
        
        num_of_nexts = len(nexts)
        if num_of_nexts > 0:
            dp_table[v-1] = 1 + sum(dp_table[next] for next in nexts) / num_of_nexts
        else:
            dp_table[v-1] = np.inf
    recursive_expected.append(dp_table[0])
    return min(recursive_expected)

if __name__ == '__main__':
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)
    expcted_values = v_to_n_expected(adjacency_matrix, n)
    print(expcted_values)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Runtime Error):
import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput():
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def edit_mat(mat, weight, edge_from, edge_to):
    copied = copy.deepcopy(mat)
    copied[edge_from, edge_to] = weight
    return copied

def depth_first_search(mat, start_node):
    to_visit = [(start_node, 0, 1.0)]    # (node, depth, expected_value)
    depth_expecteds = []  # expected value of path length from 0 to n-1
    while to_visit:
        visit, depth, expected = to_visit.pop()
        if visit == n-1:
            depth_expecteds.append(depth * expected)
        else:
            nexts = [v for v, c in enumerate(mat[visit]) if c > 0]
            if nexts:
                for next in nexts:
                    to_visit.append((next, depth+1, expected/len(nexts)))
            else:   # leaf node but not n
                depth_expecteds.append(np.inf)
    return sum(depth_expecteds)





if __name__ == "__main__":
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)

    rawcols = np.where(adjacency_matrix == 1)
    expecteds = []
    for r, c in zip(rawcols[0], rawcols[1]):
        mat = edit_mat(adjacency_matrix, 0, r, c)
        expecteds.append(depth_first_search(mat, 0))

    min_expected = np.min(expecteds)
    if np.isinf(min_expected):
        print(depth_first_search(adjacency_matrix, 0))
    else:
        print(min_expected)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput():
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def edit_mat(mat, weight, edge_from, edge_to):
    copied = copy.deepcopy(mat)
    copied[edge_from, edge_to] = weight
    return copied

def depth_first_search(mat, start_node):
    to_visit = [(start_node, 0, 1.0)]    # (node, depth, expected_value)
    depth_expecteds = []  # expected value of path length from 0 to n-1
    while to_visit:
        visit, depth, expected = to_visit.pop()
        if visit == n-1:
            depth_expecteds.append(depth * expected)
        else:
            nexts = [v for v, c in enumerate(mat[visit]) if c > 0]
            if nexts:
                for next in nexts:
                    to_visit.append((next, depth+1, expected/len(nexts)))
            else:   # leaf node but not n
                depth_expecteds.append(np.inf)
    return sum(depth_expecteds)





if __name__ == "__main__":
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)

    rawcols = np.where(adjacency_matrix == 1)
    expecteds = []
    for r, c in zip(rawcols[0], rawcols[1]):
        mat = edit_mat(adjacency_matrix, 0, r, c)
        expecteds.append(depth_first_search(mat, 0))

    min_expected = np.min(expecteds)
    if np.isinf(min_expected):
        print(depth_first_search(adjacency_matrix, 0))
    else:
        print(min_expected)

Fixed submission:
# reference: https://www.onakasuitacity.com/abc144-f/

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)):   # O(m)
    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):      # O(m)
    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):      # O(m)
    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)