Problem p02884 (python)

Fixed submission:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ts = [None]*n

def sub(x):
    global ts
    if x is not None:
        s,t = x
#         s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ins[s].remove(t)
        ds[s] -= 1
    ts[n-1] = 0
    for i in range(n-2, -1, -1):
        tt = 0
        for v in ins[i]:
            tt += (ts[v])
        ts[i] = tt/len(ins[i]) + 1
    if x is not None:
        ns[t].add(s)
        ins[s].add(t)
        ds[s] += 1
    return ts[0]
ans = sub(None)
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = max(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ps = [None]*n
ts = [None]*n

def sub(x):
    global ps,ts
    if x is not None:
        s,t = x
#         s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ds[s] -= 1
    ps[0] = 1
    ts[0] = 0
    start = 1
    for i in range(start, n):
        pp = 0
        tt = 0
        for v in ns[i]:
            if ps[v]==0:
                continue
            if ds[v]>0:
                pp += ps[v]/ds[v]
                tt += (ts[v]+1)*ps[v]/ds[v]
        ps[i] = pp
        if pp>0:
            ts[i] = tt/pp
    if x is not None:
        ns[t].add(s)
        ds[s] += 1
    return ts[n-1]
ans = sub(None)
ips = ps[:]
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = min(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ps = [None]*n
ts = [None]*n

def sub(x):
    global ps,ts
    if x is not None:
        s,t = x
#         s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ds[s] -= 1
    ps[0] = 1
    ts[0] = 0
    start = 1
    for i in range(start, n):
        pp = 0
        tt = 0
        for v in ns[i]:
            if ps[v]==0:
                continue
            if ds[v]>0:
                pp += ps[v]/ds[v]
            tt += (ts[v]+1)*ps[v]/ds[v]
        ps[i] = pp
        if pp>0:
            ts[i] = tt/pp
    if x is not None:
        ns[t].add(s)
        ds[s] += 1
    return ts[n-1]
ans = sub(None)
ips = ps[:]
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = min(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)