Problem p02587 (python)

Fixed submission:
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())
S1 = []
S2 = []
C = []
for i in range(N):
    s,c = input().split()
    S1.append(s)
    S2.append(s[::-1])
    C.append(int(c))

d_v = {('',''):0,('l',''):1,('r',''):2}
idx = 3
for i in range(N):
    s = S1[i]
    for j in range(len(s)):
        for k in range(j,len(s)):
            ss_l = s[j:k+1]
            ss_r = ss_l[::-1]
            if ss_l != ss_r:
                if ('l',ss_l) not in d_v:
                    d_v[('l',ss_l)] = idx
                    idx += 1
                if ('r',ss_r) not in d_v:
                    d_v[('r',ss_r)] = idx
                    idx += 1

edge = [[] for _ in range(len(d_v))]

for i in range(N):
    s_l = S1[i]
    s_r = S2[i]
    c = C[i]
    for lr,ss in d_v:
        if ss == '':
            if lr == '':
                t = s_l
                if t==t[::-1]:
                    t = ''
                edge[0].append((c,d_v[('l',t)]))
            else:
                continue
        if lr == 'l':
            if ss.startswith(s_r):
                t = ss[len(s_r):]
                if t==t[::-1]:
                    t = ''
                edge[d_v[(lr,ss)]].append((c,d_v[('l',t)]))
            if s_r.startswith(ss):
                t = s_r[len(ss):]
                if t==t[::-1]:
                    t = ''
                edge[d_v[(lr,ss)]].append((c,d_v[('r',t)]))
        elif lr == 'r':
            if ss.startswith(s_l):
                t = ss[len(s_l):]
                if t==t[::-1]:
                    t = ''
                edge[d_v[(lr,ss)]].append((c,d_v[('r',t)]))
            if s_l.startswith(ss):
                t = s_l[len(ss):]
                if t==t[::-1]:
                    t = ''
                edge[d_v[(lr,ss)]].append((c,d_v[('l',t)]))
            

dist = dijkstra(edge,len(d_v),0)
ans = min(dist[1],dist[2])
if ans == inf:
    ans = -1

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2*10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S1 = []
    S2 = []
    C = []
    for i in range(N):
        s,c = input().split()
        S1.append(s)
        S2.append(s[::-1])
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**18)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S1 = []
    S2 = []
    C = []
    for i in range(N):
        s,c = input().split()
        S1.append(s)
        S2.append(s[::-1])
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S1 = []
    S2 = []
    C = []
    for i in range(N):
        s,c = input().split()
        S1.append(s)
        S2.append(s[::-1])
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S1 = []
    S2 = []
    C = []
    for i in range(N):
        s,c = input().split()
         S1.append(s)
        S2.append(s[::-1])
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S = []
    C = []
    for i in range(N):
        s,c = input().split()
        S.append(s)
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S[i][::-1]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S = []
    C = []
    for i in range(N):
        s,c = input().split()
        S.append(s)
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S[i][::-1]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))
    
d_l = defaultdict(lambda:inf)
def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    if d_l[s1] != inf:
        return d_l[s1]
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_l[s1] = res
    return res

d_r = defaultdict(lambda:inf)
def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    if d_r[s2] != inf:
        return d_r[s2]
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    d_r[s2] = res
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)

Buggy submission (verdict: Runtime Error):
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)