Problem:


Score : 600 points

Problem Statement

We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.

Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.

The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.

Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.

If there is no choice of strings in which he can make a palindrome, print -1.

Constraints

1 \leq N \leq 50

1 \leq |S_i| \leq 20

S_i consists of lowercase English letters.

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 C_1
S_2 C_2
:
S_N C_N

Output

Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.

Sample Input 1

3
ba 3
abc 4
cbaa 5

Sample Output 1

7

We have ba, abc, and cbaa.

For example, we can use ba once and abc once for a cost of 7, then concatenate them in the order abc, ba to make a palindrome.
Also, we can use abc once and cbaa once for a cost of 9, then concatenate them in the order cbaa, abc to make a palindrome.

We cannot make a palindrome for a cost less than 7, so we should print 7.

Sample Input 2

2
abcab 5
cba 3

Sample Output 2

11

We can choose abcab once and cba twice, then concatenate them in the order abcab, cba, cba to make a palindrome for a cost of 11.

Sample Input 3

4
ab 5
cba 3
a 12
ab 10

Sample Output 3

8

We can choose a once, which is already a palindrome, but it is cheaper to concatenate ab and cba.

Sample Input 4

2
abc 1
ab 2

Sample Output 4

-1

We cannot make a palindrome, so we should print -1.



Sample input:
3
ba 3
abc 4
cbaa 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
from collections import deque


def isPalindrome(s):
    L = len(s)
    rst = True
    if L:
        for i in range(L // 2):
            if s[i] != s[L - 1 - i]:
                rst = False
                break
    return rst


N = int(input())
S = []
for _ in range(N):
    s, c = input().split()
    S.append((s, int(c)))

path = [dict() for _ in range(2)]
q = deque()
S.sort(key=lambda x: x[1])
for s, c in S:
    if s not in path[0] or path[0][s] > c:
        path[0][s] = c
        q.append((0, s, c))

ans = float('inf')
isPossible = False
while q:
    side, s0, c0 = q.popleft()
    if isPalindrome(s0):
        ans = min(ans, c0)
        isPossible |= True
    else:
        for s1, c1 in S:
            if side == 0:
                l = s0
                r = s1
            else:
                l = s1
                r = s0

            if len(l) > len(r):
                for i in range(len(r)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = l[len(r):]
                    nc = c0 + c1
                    side = 0
                    if (ns not in path[side]) or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            elif len(l) < len(r):
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = r[:-len(l)]
                    nc = c0 + c1
                    side = 1
                    if (ns not in path[side]) or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            else:
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = ''
                    nc = c0 + c1
                    side = 0
                    if (ns not in path[side]) or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
if isPossible:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 150
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def isPalindrome(s):
    L = len(s)
    rst = True
    if L:
        for i in range(L // 2):
            if s[i] != s[L - 1 - i]:
                rst = False
                break
    return rst


N = int(input())
S = []
for _ in range(N):
    s, c = input().split()
    S.append((s, int(c)))

path = [dict() for _ in range(2)]
q = deque()
S.sort(key=lambda x: x[1])
for s, c in S:
    if s not in path[0] or path[0][s] > c:
        path[0][s] = c
        q.append((0, s, c))

ans = float('inf')
isPossible = False
while q:
    side, s0, c0 = q.popleft()
    if isPalindrome(s0):
        ans = min(ans, c0)
        isPossible |= True
    else:
        for s1, c1 in S:
            if side == 0:
                l = s0
                r = s1
            else:
                l = s1
                r = s0

            if len(l) > len(r):
                for i in range(len(r)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = l[len(r):]
                    nc = c0 + c1
                    side = 0
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            elif len(l) < len(r):
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = r[:-len(l)]
                    nc = c0 + c1
                    side = 1
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            else:
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = ''
                    nc = c0 + c1
                    side = 0
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
if isPossible:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def isPalindrome(s):
    L = len(s)
    rst = True
    if L:
        for i in range(L // 2):
            if s[i] != s[L - 1 - i]:
                rst = False
                break
    return rst


N = int(input())
S = []
for _ in range(N):
    s, c = input().split()
    S.append((s, int(c)))

path = [dict() for _ in range(2)]
q = deque()
for s, c in S:
    if s not in path[0] or path[0][s] > c:
        path[0][s] = c
        q.append((0, s, c))

ans = float('inf')
isPossible = False
while q:
    side, s0, c0 = q.popleft()
    if isPalindrome(s0):
        ans = min(ans, c0)
        isPossible |= True
    else:
        for s1, c1 in S:
            if side == 0:
                l = s0
                r = s1
            else:
                l = s1
                r = s0

            if len(l) > len(r):
                for i in range(len(r)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = l[len(r):]
                    nc = c0 + c1
                    side = 0
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            elif len(l) < len(r):
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = r[:-len(l)]
                    nc = c0 + c1
                    side = 1
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
            else:
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = ''
                    nc = c0 + c1
                    side = 0
                    if ns not in path[side] or path[side][ns] > nc:
                        path[side][ns] = nc
                        q.append((side, ns, nc))
if isPossible:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, heapq, math

input = sys.stdin.readline
N = int(input())
SC = []
for _ in range(N):
    S, C = input().split()
    SC.append((S, int(C)))

nodes = dict()
nodes['S'] = []
for s, c in SC:
    for i in range(len(s)+1):
        nodes['L'+s[i:]] = []
        nodes['R'+s[-i::-1]] = []
for node in nodes.keys():
    for s, c in SC:
        if node[0] == 'L':
            if s[::-1].startswith(node[1:]):
                nodes[node].append(('R' + s[-len(node)::-1], c))
            elif node[1:].startswith(s[::-1]):
                nodes[node].append(('L' + node[1 + len(s):], c))
        elif node[0] == 'R':
            if s.startswith(node[1:]):
                nodes[node].append(('L' + s[len(node)-1:], c))
            elif node[1:].startswith(s):
                nodes[node].append(('R' + node[1 + len(s):], c))
for s, c in SC:
    nodes['S'].append(('L' + s, c))
    nodes['S'].append(('R' + s[::-1], c))
nodes['L'] = [('G', 0)]
nodes['R'] = [('G', 0)]
for node in nodes.keys():
    if len(set(node[1:])) == 1:
        nodes[node].append(('G', 0))

HQ = [(0, 'S')]
heapq.heapify(HQ)
ans = -1
while len(HQ)>0:
    c, node = heapq.heappop(HQ)
    if node == 'G':
        ans = c
        break
    for node_, c_ in nodes[node]:
        heapq.heappush(HQ, (c+c_, node_))
    nodes[node] = []

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, heapq, math

input = sys.stdin.readline
N = int(input())
SC = []
for _ in range(N):
    S, C = input().split()
    SC.append((S, int(C)))

nodes = dict()
nodes['S'] = []
for s, c in SC:
    for i in range(len(s)+1):
        nodes['L'+s[i:]] = []
        nodes['R'+s[-i::-1]] = []
for node in nodes.keys():
    for s, c in SC:
        if node[0] == 'L':
            if s[::-1].startswith(node[1:]):
                nodes[node].append(('R' + s[-len(node)::-1], c))
            elif node[1:].startswith(s[::-1]):
                nodes[node].append(('L' + node[1 + len(s):], c))
        elif node[0] == 'R':
            if s.startswith(node[1:]):
                nodes[node].append(('L' + s[len(node)-1:], c))
            elif node[1:].startswith(s):
                nodes[node].append(('R' + node[1 + len(s):], c))
for s, c in SC:
    nodes['S'].append(('L' + s, c))
    nodes['S'].append(('R' + s[::-1], c))
nodes['L'] = [('G', 0)]
nodes['R'] = [('G', 0)]
for node in nodes.keys():
    if len(node) == 2:
        nodes[node].append(('G', 0))

HQ = [(0, 'S')]
heapq.heapify(HQ)
ans = -1
while len(HQ)>0:
    c, node = heapq.heappop(HQ)
    if node == 'G':
        ans = c
        break
    for node_, c_ in nodes[node]:
        heapq.heappush(HQ, (c+c_, node_))
    nodes[node] = []

print(ans)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
inf = 10**18
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))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    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)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    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)
        return res

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

if ans == inf:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = []
C = []
for _ in range(N):
  s, c = input().split()
  C.append(int(c))
  S.append(tuple(ord(c) - ord('a') for c in s))
#print(S)
INF = 10**30
dp = {}
def min_cost(l, r):
  if (l, r) in dp:
    return dp[(l, r)]
  if l and l == l[::-1]:
    dp[(l, r)] = 0
    return dp[(l, r)]
  if r and r == r[::-1]:
    dp[(l, r)] = 0
    return dp[(l, r)]
    
  #print(l, r)
  dp[(l, r)] = INF
  if not l:
    for c, s in zip(C, S):
      if len(s) >= len(r):
        if s[len(s)-len(r):] == r:
          dp[(l, r)] = min(dp[(l, r)], c + min_cost(s[:len(s)-len(r)][::-1], () ))
      elif len(s) == len(r):
        if s == r:
          dp[(l, r)] = min(dp[(l, r)], c)
      else:
        if s == r[len(r)-len(s):]:
          dp[(l, r)] = min(dp[(l, r)], c + min_cost((), r[:len(r)-len(s)]))
        
  if not r:
    for c, s in zip(C, S):
      if len(s) >= len(l):
        #print('equal', s[:len(l)] , l)
        if s[:len(l)] == l:
          dp[(l, r)] = min(dp[(l, r)], c + min_cost((), s[len(l):][::-1] ))
      elif len(s) == len(l):
        if s == l:
          dp[(l, r)] = min(dp[(l, r)], c)
      else:
        if s == l[:len(s)]:
          dp[(l, r)] = min(dp[(l, r)], c + min_cost(l[len(s):], ()))
        
  return dp[(l, r)]
        
  
m = min_cost((), ())
for s, c in zip(S, C):
  if s == s[::-1]:
    m = min(m, c)
if m == INF:
  print(-1)
else:
  print(m)

Submission status: Wrong Answer

Solution code:
inf = 10**18
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))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    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)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    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)
        return res

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

if ans >= inf:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
inf = 10**18
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))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    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)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    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)
        return res

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

if ans == inf:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]

for i in range(N):
    ST[i][1]=int(ST[i][1])

ST.sort()

ST2=[]
for i in range(N):
    if i>0 and ST[i][0]==ST[i-1][0]:
        continue
    ST2.append((ST[i][0],ST[i][1]))
ST=ST2


FDICT=dict()
BDICT=dict()

for s,i in ST:
    FDICT[s[::-1]]=i
    BDICT[s[::-1]]=i

    for j in range(1,len(s)):
        if not(s[:j][::-1] in BDICT):
            BDICT[s[:j][::-1]]=1<<60
        if not(s[-j:][::-1] in FDICT):
            FDICT[s[-j:][::-1]]=1<<60

ANS=1<<60
flag=0
for rep in range(1<<60):
    flag=0
    for f in FDICT:
        lf=len(f)
        for s,i in ST:
            ls=len(s)

            if lf == ls:
                if s==f:
                    ANS=min(ANS,FDICT[f]+i)
            elif ls>lf:
                if s[-lf:]==f and BDICT[s[:-lf][::-1]]>FDICT[f]+i:
                    BDICT[s[:-lf][::-1]]=FDICT[f]+i
                    flag=1
            else:
                if f[-ls:]==s and FDICT[f[:-ls]]>FDICT[f]+i:
                    FDICT[f[:-ls]]=FDICT[f]+i
                    flag=1
                    

    for b in BDICT:
        lb=len(b)
        for s,i in ST:
            ls=len(s)

            if lb == ls:
                if s==b:
                    ANS=min(ANS,BDICT[b]+i)
            elif ls>lb:
                if s[:lb]==b and FDICT[s[-lb:][::-1]]>BDICT[b]+i:
                    FDICT[s[-lb:][::-1]]=BDICT[b]+i
                    flag=1
                    
            else:
                if b[:ls]==s and BDICT[b[ls:]]>BDICT[b]+i:
                    BDICT[b[ls:]]=BDICT[b]+i
    if flag==0:
        break
                    

for f in FDICT:
    if f==f[::-1]:
        ANS=min(ANS,FDICT[f])

for b in BDICT:
    if b==b[::-1]:
        ANS=min(ANS,BDICT[b])

if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]

for i in range(N):
    ST[i][1]=int(ST[i][1])

ST.sort()

ST2=[]
for i in range(N):
    if i>0 and ST[i][0]==ST[i-1][0]:
        continue
    ST2.append((ST[i][0],ST[i][1]))
ST=ST2


FDICT=dict()
BDICT=dict()

for s,i in ST:
    FDICT[s[::-1]]=i
    BDICT[s[::-1]]=i

    for j in range(1,len(s)):
        if not(s[:j][::-1] in BDICT):
            BDICT[s[:j][::-1]]=1<<60
        if not(s[-j:][::-1] in FDICT):
            FDICT[s[-j:][::-1]]=1<<60

ANS=1<<100
for rep in range(2100):
    for f in FDICT:
        lf=len(f)
        for s,i in ST:
            ls=len(s)

            if lf == ls:
                if s==f:
                    ANS=min(ANS,FDICT[f]+i)
            elif ls>lf:
                if s[-lf:]==f:
                    BDICT[s[:-lf][::-1]]=min(BDICT[s[:-lf][::-1]],FDICT[f]+i)
            else:
                if f[-ls:]==s:
                    FDICT[f[:-ls]]=min(FDICT[f[:-ls]],FDICT[f]+i)

    for b in BDICT:
        lb=len(b)
        for s,i in ST:
            ls=len(s)

            if lb == ls:
                if s==b:
                    ANS=min(ANS,BDICT[b]+i)
            elif ls>lb:
                if s[:lb]==b:
                    FDICT[s[-lb:][::-1]]=min(FDICT[s[-lb:][::-1]],BDICT[b]+i)
            else:
                if b[:ls]==s:
                    BDICT[b[ls:]]=min(BDICT[b[ls:]],BDICT[b]+i)

for f in FDICT:
    if f==f[::-1]:
        ANS=min(ANS,FDICT[f])

for b in BDICT:
    if b==b[::-1]:
        ANS=min(ANS,BDICT[b])

if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]

for i in range(N):
    ST[i][1]=int(ST[i][1])


FDICT=dict()
BDICT=dict()

for s,i in ST:
    FDICT[s[::-1]]=i
    BDICT[s[::-1]]=i

    for j in range(1,len(s)):
        if not(s[:j][::-1] in BDICT):
            BDICT[s[:j][::-1]]=1<<60
        if not(s[-j:][::-1] in FDICT):
            FDICT[s[-j:][::-1]]=1<<60

ANS=1<<100
for rep in range(2500):
    for f in FDICT:
        lf=len(f)
        for s,i in ST:
            ls=len(s)

            if lf == ls:
                if s==f:
                    ANS=min(ANS,FDICT[f]+i)
            elif ls>lf:
                if s[-lf:]==f:
                    BDICT[s[:-lf][::-1]]=min(BDICT[s[:-lf][::-1]],FDICT[f]+i)
            else:
                if f[-ls:]==s:
                    FDICT[f[:-ls]]=min(FDICT[f[:-ls]],FDICT[f]+i)

    for b in BDICT:
        lb=len(b)
        for s,i in ST:
            ls=len(s)

            if lb == ls:
                if s==b:
                    ANS=min(ANS,BDICT[b]+i)
            elif ls>lb:
                if s[:lb]==b:
                    FDICT[s[-lb:][::-1]]=min(FDICT[s[-lb:][::-1]],BDICT[b]+i)
            else:
                if b[:ls]==s:
                    BDICT[b[ls:]]=min(BDICT[b[ls:]],BDICT[b]+i)

for f in FDICT:
    if f==f[::-1]:
        ANS=min(ANS,FDICT[f])

for b in BDICT:
    if b==b[::-1]:
        ANS=min(ANS,BDICT[b])

if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]

for i in range(N):
    ST[i][1]=int(ST[i][1])


FDICT=dict()
BDICT=dict()

for s,i in ST:
    FDICT[s[::-1]]=i
    BDICT[s[::-1]]=i

    for j in range(1,len(s)):
        if not(s[:j][::-1] in BDICT):
            BDICT[s[:j][::-1]]=1<<60
        if not(s[-j:][::-1] in FDICT):
            FDICT[s[-j:][::-1]]=1<<60

ANS=1<<100
for rep in range(1000):
    for f in FDICT:
        lf=len(f)
        for s,i in ST:
            ls=len(s)

            if lf == ls:
                if s==f:
                    ANS=min(ANS,FDICT[f]+i)
            elif ls>lf:
                if s[-lf:]==f:
                    BDICT[s[:-lf][::-1]]=min(BDICT[s[:-lf][::-1]],FDICT[f]+i)
            else:
                if f[-ls:]==s:
                    FDICT[f[:-ls]]=min(FDICT[f[:-ls]],FDICT[f]+i)

    for b in BDICT:
        lb=len(b)
        for s,i in ST:
            ls=len(s)

            if lb == ls:
                if s==b:
                    ANS=min(ANS,BDICT[b]+i)
            elif ls>lb:
                if s[:lb]==b:
                    FDICT[s[-lb:][::-1]]=min(FDICT[s[-lb:][::-1]],BDICT[b]+i)
            else:
                if b[:ls]==s:
                    BDICT[b[ls:]]=min(BDICT[b[ls:]],BDICT[b]+i)

for f in FDICT:
    if f==f[::-1]:
        ANS=min(ANS,FDICT[f])

for b in BDICT:
    if b==b[::-1]:
        ANS=min(ANS,BDICT[b])

if ANS==1<<60:
    print(-1)
else:
    print(ANS)

Submission status: Wrong Answer

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


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
sc = [None]*n
nodes = []
for i in range(n):
    s,c = input().split()
    c = int(c)
    sc[i] = (s,c)
    nodes.extend([(0,s[i:]) for i in range(len(s))])
    nodes.extend([(1,s[:i]) for i in range(1, len(s)+1)])

for u in nodes:
    for s,c in sc:
        if u[0]==0 and s.endswith(u[1][::-1]):
            v = (1, s[:-len(u[1])])
            ns[u].add((c,v))
        elif u[0]==0 and u[1][::-1].endswith(s):
            v = (0, u[1][len(s):])
            ns[u].add((c,v))
        elif u[0]==1 and s.startswith(u[1][::-1]):
            v = (0, s[len(u[1]):])
            ns[u].add((c,v))
        elif u[0]==1 and u[1][::-1].startswith(s):
            v = (1, u[1][:-len(s)])
            ns[u].add((c,v))
start = 0
for s,c in sc:
    ns[start].add((c, (0,s)))
    ns[start].add((c, (1,s)))
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(start)
ans = float("inf")
l = [chr(v) for v in range(ord("a"), ord("z")+1)] + [""]
for k in [(i,cc) for i in range(2) for cc in l]:
    if k in vals:
        ans = min(ans, vals[k])

for s,c in sc:
    if s==s[::-1]:
        ans = min(ans, c)
if ans==float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

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


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
sc = [None]*n
nodes = []
for i in range(n):
    s,c = input().split()
    c = int(c)
    sc[i] = (s,c)
    nodes.extend([(0,s[i:]) for i in range(len(s))])
    nodes.extend([(1,s[:i]) for i in range(1, len(s)+1)])

for u in nodes:
    for s,c in sc:
#         if u[0]==0 and u[1][::-1]==s[-len(u[1]):]:
        if u[0]==0 and s.endswith(u[1][::-1]):
            v = (1, s[:-len(u[1])])
            ns[u].add((c,v))
        elif u[0]==0 and u[1][::-1].endswith(s):
            v = (0, u[1][len(s):])
            ns[u].add((c,v))
#         elif u[0]==1 and u[1][::-1]==s[:len(u[1])]:
        elif u[0]==1 and s.startswith(u[1][::-1]):
            v = (0, s[len(u[1]):])
            ns[u].add((c,v))
        elif u[0]==1 and u[1][::-1].startswith(s):
            v = (1, u[1][:-len(s)])
            ns[u].add((c,v))
start = 0
for s,c in sc:
    ns[start].add((c, (0,s)))
    ns[start].add((c, (1,s)))
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(start)
ans = float("inf")
l = [chr(v) for v in range(ord("a"), ord("z")+1)]
for k in [(i,cc) for i in range(2) for cc in l]:
    if k in vals:
        ans = min(ans, vals[k])

for s,c in sc:
    if s==s[::-1]:
        ans = min(ans, c)
if ans==float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

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


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
sc = [None]*n
nodes = []
for i in range(n):
    s,c = input().split()
    c = int(c)
    sc[i] = (s,c)
    nodes.extend([(0,s[i:]) for i in range(len(s))])
    nodes.extend([(1,s[:i]) for i in range(1, len(s)+1)])

for u in nodes:
    for s,c in sc:
        if u[0]==0 and u[1][::-1]==s[-len(u[1]):]:
            v = (1, s[:-len(u[1])])
            ns[u].add((c,v))
        elif u[0]==1 and u[1][::-1]==s[:len(u[1])]:
            v = (0, s[len(u[1]):])
            ns[u].add((c,v))
start = 0
for s,c in sc:
    ns[start].add((c, (0,s)))
    ns[start].add((c, (1,s)))
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(start)
ans = float("inf")
for k in [(1, ""), (0, "")]:
    if k in vals:
        ans = min(ans, vals[k]//2)

for s,c in sc:
    if s==s[::-1]:
        ans = min(ans, c)
if ans==float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
import copy

n = int(input())
original = []
for _ in range(n):
    s,c = input().split();c=int(c)
    original.append((c,s))

heapq.heapify(original)
hp = copy.deepcopy(original)
flag = 0
answer = 0
while not len(hp)==0:
    #print(hp)
    if flag:
        break
    c_temp,s_temp = heapq.heappop(hp)
    if len(s_temp)==1:
        flag = 1
        answer = c_temp
    else:
        for c,s in original:
            if len(s_temp)==len(s):
                if s_temp == s[::-1]:
                    flag = 1
                    answer = c_temp+c
            elif len(s_temp) > len(s):
                if s_temp[:len(s)]==s[::-1]:
                    heapq.heappush(hp,(c_temp+c,s_temp[len(s):]))
            else:
                if s_temp == s[::-1][:len(s_temp)]:
                    heapq.heappush(hp,(c_temp+c,s[:len(s)-len(s_temp)]))
if flag:
    print(answer)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
import copy

n = int(input())
original = []
for _ in range(n):
    s,c = input().split();c=int(c)
    original.append((c,s))

heapq.heapify(original)
hp = copy.deepcopy(original)
flag = 0
answer = 0
while not len(hp)==0:
    #print(hp)
    if flag:
        break
    c_temp,s_temp = heapq.heappop(hp)
    if len(s_temp)==1:
        flag = 1
        answer = c_temp
    else:
        for c,s in original:
            if len(s_temp)==len(s):
                if s_temp == s[::-1]:
                    flag = 1
                    answer = c_temp+c
            elif len(s_temp) > len(s):
                if s_temp[:len(s)]==s[::-1]:
                    heapq.heappush(hp,(c_temp+c,s_temp[:len(s)]))
            else:
                if s_temp == s[::-1][:len(s_temp)]:
                    heapq.heappush(hp,(c_temp+c,s[:len(s)-len(s_temp)]))
if flag:
    print(answer)
else:
    print(-1)