Problem p02884 (python)

Fixed submission:
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_in = [0] * (N+1)  # ノードに到着するまでの辺の個数の期待値
#
# for v, edge_in in enumerate(Edge_in[2:], 2):
#     p_sum = 0
#     su = 0
#     for u in edge_in:
#         p = P_edge[u]
#         p_sum += p
#         su += p * E_node_in[u]
#     su /= p_sum
#     su += 1
#     E_node_in[v] = su

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 = e_all = E_node_out[1]
# for s, t in ST:
#     p_st = P_edge[s]
#     e_st = E_node_in[s] + E_node_out[t] + 1
#     print("e_st,p_st=",e_st,p_st)
#     a = (e_all - p_st*e_st) / (1 - p_st)
#     print("s,t,a=",s,t,a)
#     ans = min(ans, a)

ans = 0
for s, t in ST:
    p_s = P_node[s]
    #p_st = P_edge[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])
    #print("s,t,a=", s, t, a)
    ans = min(ans, a)
print(ans + E_node_out[1])

Buggy submission (verdict: Runtime Error):
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_in = [0] * (N+1)  # ノードに到着するまでの辺の個数の期待値

for v, edge_in in enumerate(Edge_in[2:], 2):
    p_sum = 0
    su = 0
    for u in edge_in:
        p = P_edge[u]
        p_sum += p
        su += p * E_node_in[u]
    su /= p_sum
    su += 1
    E_node_in[v] = su

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 = e_all = E_node_out[1]
# for s, t in ST:
#     p_st = P_edge[s]
#     e_st = E_node_in[s] + E_node_out[t] + 1
#     print("e_st,p_st=",e_st,p_st)
#     a = (e_all - p_st*e_st) / (1 - p_st)
#     print("s,t,a=",s,t,a)
#     ans = min(ans, a)

ans = 0
for s, t in ST:
    p_s = P_node[s]
    p_st = P_edge[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])
    #print("s,t,a=", s, t, a)
    ans = min(ans, a)
print(ans + E_node_out[1])

Buggy submission (verdict: Runtime Error):
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_in = [0] * (N+1)  # ノードに到着するまでの辺の個数の期待値

for v, edge_in in enumerate(Edge_in[2:], 2):
    p_sum = 0
    su = 0
    for u in edge_in:
        p = P_edge[u]
        p_sum += p
        su += p * E_node_in[u]
    su /= p_sum
    su += 1
    E_node_in[v] = su

E_node_out = [0] * (N+1)  # ノードから出発したあと通る辺の個数の期待値