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 defaultdict
from heapq import heappush, heappop
def main():
    N = int(input())
    SC = []
    SCrev = []
    for _ in range(N):
        s, c = input().split()
        c = int(c)
        SC.append((s, c))
        SCrev.append((s[::-1], c))
    dist = defaultdict(lambda: 10**18)
    start = ("", "")
    dist[start] = 0
    q = [(0, "", "")]
    while q:
        dist_v, vl, vr = heappop(q)
        if (dist_v>0 and len(vl)==0 and len(vr)==0) or (len(vl) and vl == vl[::-1]) or (len(vr) and vr == vr[::-1]):
            print(dist_v)
            exit()
        if dist[(vl, vr)] != dist_v:
            continue
        if len(vl) < len(vr):
            for s, c in SC:
                if len(s) <= len(vr):
                    if vr.startswith(s):
                        vr_ = vr[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
                else:
                    if s.startswith(vr):
                        vl_ = s[len(vr):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
        else:
            for s, c in SCrev:
                if len(s) <= len(vl):
                    if vl.startswith(s):
                        vl_ = vl[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
                else:
                    if s.startswith(vl):
                        vr_ = s[len(vl):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
def main():
    N = int(input())
    SC = []
    SCrev = []
    for _ in range(N):
        s, c = input().split()
        c = int(c)
        SC.append((s, c))
        SCrev.append((s[::-1], c))
    dist = defaultdict(lambda: 10**18)
    start = ("", "")
    dist[start] = 0
    q = [(0, "", "")]
    while q:
        dist_v, vl, vr = heappop(q)
        if (len(vl) and vl == vl[::-1]) or (len(vr) and vr == vr[::-1]):
            print(dist_v)
            exit()
        if dist[(vl, vr)] != dist_v:
            continue
        if len(vl) < len(vr):
            for s, c in SC:
                if len(s) <= len(vr):
                    if vr.startswith(s):
                        vr_ = vr[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
                else:
                    if s.startswith(vr):
                        vl_ = s[len(vr):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
        else:
            for s, c in SCrev:
                if len(s) <= len(vl):
                    if vl.startswith(s):
                        vl_ = vl[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
                else:
                    if s.startswith(vl):
                        vr_ = s[len(vl):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[None]*n
c=[None]*n
for i in range(n):
  s_i,c_i=input().split()
  s[i]=s_i
  c[i]=int(c_i)
score=100000000000000
#print(s)
for i in range(n):
  for j in range(n):
    for k in range(n):
      for l in range(n):
        s0="".join([s[i],s[j]])
        s1="".join([s[i],s[k]])
        s2="".join([s[i],s[l]])
        s3="".join([s[i],s[j],s[k]])
        s4="".join([s[i],s[k],s[l]])
        s5="".join([s[i],s[j],s[k],s[l]])
        if s0==s0[::-1]:
          score=min(score,c[i]+c[j])
        if s1==s1[::-1]:
          score=min(score,c[i]+c[k])
        if s2==s2[::-1]:
          score=min(score,c[i]+c[l])
        if s3==s3[::-1]:
          score=min(score,c[i]+c[j]+c[k])
        if s4==s4[::-1]:
          score=min(score,c[i]+c[k]+c[l])
        if s5==s5[::-1]:
          score=min(score,c[i]+c[j]+c[k]+c[l])
        #print(s0)
if score==100000000000000:
  print(-1)
else:
  print(score)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
def main():
    N = int(input())
    SC = []
    SCrev = []
    for _ in range(N):
        s, c = input().split()
        c = int(c)
        SC.append((s, c))
        SCrev.append(("".join(s[::-1]), c))
    dist = defaultdict(lambda: 10**18)
    start = ("", "")
    dist[start] = 0
    q = [(0, "", "")]
    while q:
        dist_v, vl, vr = heappop(q)
        if dist_v != 0 and len(vl) + len(vr) <= 1:
            print(dist_v)
            exit()
        if dist[(vl, vr)] != dist_v:
            continue
        if len(vl) < len(vr):
            for s, c in SC:
                if len(s) <= len(vr):
                    if vr.startswith(s):
                        vr_ = vr[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
                else:
                    if s.startswith(vr):
                        vl_ = s[len(vr):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
        else:
            for s, c in SCrev:
                if len(s) <= len(vl):
                    if vl.startswith(s):
                        vl_ = vl[len(s):]
                        dist_u = dist_v + c
                        if dist_u < dist[(vl_, "")]:
                            dist[(vl_, "")] = dist_u
                            heappush(q, (dist_v+c, vl_, ""))
                else:
                    if s.startswith(vl):
                        vr_ = s[len(vl):]
                        dist_u = dist_v + c
                        if dist_u < dist[("", vr_)]:
                            dist[("", vr_)] = dist_u
                            heappush(q, (dist_v+c, "", vr_))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())
import time
sys.setrecursionlimit(1000000)
lim=100
start = time.time()
def solve():
    def dfs(pre, suf,nu):
        if time.time() > start+1:
            return float("inf")
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        if len(pre) <= len(suf):
            k = suf[len(pre):]
            for i in range(n):
                s = lis[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre+s,suf,nu+1)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s,nu+1)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    n = I()
    lis = []
    c = []
    rev = []
    for _ in range(n):
        a,b = input().split()
        b = int(b)
        a = list(a)
        lis.append(a)
        rev.append(a[::-1])
        c.append(b)
    ans = dfs([],[],0)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())

sys.setrecursionlimit(1000000)
lim=100
def solve():
    def dfs(pre, suf,nu):
        if nu >= n:
            return float("inf")
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        if len(pre) <= len(suf):
            k = suf[len(pre):]
            for i in range(n):
                s = lis[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre+s,suf,nu+1)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s,nu+1)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    n = I()
    lis = []
    c = []
    rev = []
    for _ in range(n):
        a,b = input().split()
        b = int(b)
        a = list(a)
        lis.append(a)
        rev.append(a[::-1])
        c.append(b)
    ans = dfs([],[],0)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

def dfs(v):
    CC = 10**18
    ff = 0
    if v in gs:
        return 1, 0
    for u, c in G[v]:
        if u in vs:
            continue
        vs.add(u)
        if u in gs:
            return 1, c
        f, c2 = dfs(u)
        if f:
            ff = 1
            CC = min(CC, c2+c)
    return ff, CC

def han(s):
    n = len(s)
    for i in range(n):
        if s[i] != s[n-i-1]:
            return 0
    return 1


N, = map(int, input().split())
R = []
L = []
for _ in range(N):
    s, c = input().split()
    t = s[::-1]
    c = int(c)
    for i in range(len(s)+1):
        R.append((s[i:], s[:i], c))
        L.append((t[i:], t[:i], c))
M = len(R)
G = [set() for _ in range(M*2)]
gs = set()
starts = list()
for i in range(M):
    r = R[i]
    if r[1] == "":
        starts.append(i)
    if L[i][1] == "":
        starts.append(i+M)
    if han(r[0]):
        gs.add(i)
    if han(L[i][0]):
        gs.add(i+M)
    for j in range(M):
        l = L[j]
        if r[0] == l[1]:
            G[i].add((M+j, l[2]))
        if r[1] == l[0]:
            G[j+M].add((i, r[2]))

vs = set()
RR = 10**18
for s in starts:
    cc = R[s][2] if s < M else L[s-M][2]
    f, A = dfs(s)
    if f:
        RR = min(A+cc, RR)
if RR == 10**18:
    print(-1)
else:
    print(RR)

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 << 60
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:
                    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:
                    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 << 58 else -1)

Submission status: Wrong Answer

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 60
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 << 60
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:
                    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:
                    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 << 58 else -1)

Submission status: Wrong Answer

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 120
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 << 60
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:
                    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:
                    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:
import sys
input = sys.stdin.readline

N=int(input())
ST=[input().split() for i in range(N)]
L=0
for i in range(N):
    ST[i][1]=int(ST[i][1])
    L+=len(ST[i][0])

DICT=dict()

for x,i in ST:
    if x in DICT:
        DICT[x]=min(DICT[x],i)
    else:
        DICT[x]=i

for rep in range(20):
    for d in list(DICT.keys()):
        for x,i in ST:
            if not(d+x in DICT):
                if len(d)+len(x)<=L:
                    DICT[d+x]=DICT[d]+i
            elif DICT[d+x]>DICT[d]+i:
                DICT[d+x]=DICT[d]+i

ANS=1<<100

for d in DICT:
    for j in DICT:
        if d==j[::-1] or j==d[::-1] or (len(d)>=2 and d[:-1]==j[::-1]) or (len(d)>=2 and d[1:]==j[::-1]):
            ANS=min(ANS,DICT[d]+DICT[j])

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

Submission status: Wrong Answer

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
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 = randrange(1 << 60)
D[r] = (0, "", 0)
H = [r]
ans = 1 << 60
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:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        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:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << 58 else -1)

Submission status: Wrong Answer

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

def dfs(v):
    CC = 10**18
    ff = 0
    if v in gs:
        return 1, 0
    for u, c in G[v]:
        if u in vs:
            continue
        vs.add(u)
        if u in gs:
            return 1, c
        f, c2 = dfs(u)
        if f:
            ff = 1
            CC = min(CC, c2+c)
    return ff, CC

def han(s):
    n = len(s)
    for i in range(n):
        if s[i] != s[n-i-1]:
            return 0
    return 1


N, = map(int, input().split())
R = []
L = []
for _ in range(N):
    s, c = input().split()
    t = s[::-1]
    c = int(c)
    for i in range(len(s)+1):
        R.append((s[i:], s[:i], c))
        L.append((t[i:], t[:i], c))
#print(R)
#print(L)
M = len(R)
G = [set() for _ in range(M*2)]
gs = set()
starts = list()
for i in range(M):
    r = R[i]
    if r[1] == "":
        starts.append(i)
    if han(r[0]):
        gs.add(i)
    if han(L[i][0]):
        gs.add(i+M)
    for j in range(M):
        l = L[j]
        if r[1] == l[0]:
            G[j+M].add((i, r[2]))
        if r[0] == l[1]:
            G[i].add((M+j, l[2]))

vs = set()
RR = 10**18
for s in starts:
    vs.add(s)
    cc = R[s][2]
    f, A = dfs(s)
    if f:
        RR = min(A+cc, RR)
#        print("R",A+cc)
    f, A = dfs(s+M)
    if f:
        RR = min(A+cc, RR)
#        print("R",A+cc)
if RR == 10**18:
    print(-1)
else:
    print(RR)

Submission status: Wrong Answer

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

N=int(input())
ST=[input().split() for i in range(N)]
L=0
for i in range(N):
    ST[i][1]=int(ST[i][1])
    L+=len(ST[i][0])

DICT=dict()

for x,i in ST:
    if x in DICT:
        DICT[x]=min(DICT[x],i)
    else:
        DICT[x]=i

for rep in range(50):
    for d in list(DICT.keys()):
        for x,i in ST:
            if not(d+x in DICT):
                if len(d)+len(x)<=L:
                    DICT[d+x]=DICT[d]+i
            elif DICT[d+x]>DICT[d]+i:
                DICT[d+x]=DICT[d]+i

ANS=1<<100

for d in DICT:
    for j in DICT:
        if d==j[::-1] or j==d[::-1] or (len(d)>=2 and d[:-1]==j[::-1]) or (len(d)>=2 and d[1:]==j[::-1]):
            ANS=min(ANS,DICT[d]+DICT[j])

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

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[list(input().split()) for i in range(N)]
for i in range(N):
  X[i][1]=int(X[i][1])
INF=10**18
def f(S,b):
  r=INF
  t=0
  for i in range(N):
    T=S+X[i][0]
    if T==T[::-1]:
      r=min(r,X[i][1])
  if r!=INF:
    return r
  for i in range(N):
    if len(S)>=len(X[i][0]):
      if S[:len(X[i][0])]==X[i][0][::-b]:
        r=min(r,f(S[len(X[i][0]):],b)+X[i][1])
    elif len(S)*2>len(X[i][0]):
      if X[i][0][:len(S)]==S[::b]:
        r=min(r,f(X[i][0][:len(S)],-b)+X[i][1])
  return r

P=INF
for i in range(N):
  P=min(P,f(X[i][0],1)+X[i][1])
if P!=INF:
  print(P)
else:
  print(-1)

Submission status: Wrong Answer

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

def dfs(v):
    CC = 10**18
    ff = 0
    if v in gs:
        return 1, 0
    for u, c in G[v]:
        if u in vs:
            continue
        vs.add(u)
        if u in gs:
            return 1, c
        f, c2 = dfs(u)
        if f:
            ff = 1
            CC = min(CC, c2+c)
    return ff, CC

def han(s):
    n = len(s)
    for i in range(n):
        if s[i] != s[n-i-1]:
            return 0
    return 1


N, = map(int, input().split())
R = []
L = []
for _ in range(N):
    s, c = input().split()
    t = s[::-1]
    c = int(c)
    for i in range(len(s)+1):
        R.append((s[i:], s[:i], c))
        L.append((t[i:], t[:i], c))
#print(R)
#print(L)
M = len(R)
G = [set() for _ in range(M*2)]
gs = set()
starts = list()
for i in range(M):
    r = R[i]
    if r[1] == "":
        starts.append(i)
    if han(r[0]):
        gs.add(i)
        gs.add(i+M)
    for j in range(M):
        l = L[j]
        if r[1] == l[0]:
            G[j+M].add((i, r[2]))
        if r[0] == l[1]:
            G[i].add((M+j, l[2]))

vs = set()
#print(dfs(12))
#print("st")
#print(gs)
RR = 10**18
for s in starts:
    vs.add(s)
    cc = R[s][2]
    f, A = dfs(s)
#    print("c",s)
    if f:
        RR = min(A+cc, RR)
#        print("R",A+cc)
#    print("c",s+M)
    f, A = dfs(s+M)
    if f:
        RR = min(A+cc, RR)
#        print(cc)
#        print("R",A+cc)
if RR == 10**18:
    print(-1)
else:
    print(RR)

Submission status: Wrong Answer

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop

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 = randrange(1 << 60)
D[r] = (0, "", 0)
H = [r]
ans = 1 << 60
while H:
    r = heappop(H)
    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:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        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:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << 58 else -1)

Submission status: Wrong Answer

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

def dfs(v):
    CC = 10**18
    ff = 0
    if v in gs:
        return 1, 0
    for u, c in G[v]:
        if u in vs:
            continue
        vs.add(u)
        if u in gs:
            return 1, c
        f, c2 = dfs(u)
        if f:
            ff = 1
            CC = min(CC, c2+c)
    return ff, CC


N, = map(int, input().split())
R = []
L = []
for _ in range(N):
    s, c = input().split()
    t = s[::-1]
    c = int(c)
    for i in range(len(s)+1):
        R.append((s[i:], s[:i], c))
        L.append((t[i:], t[:i], c))
#print(R)
#print(L)
M = len(R)
G = [set() for _ in range(M*2)]
gs = set()
starts = list()
for i in range(M):
    r = R[i]
    if r[1] == "":
        starts.append(i)
    if len(r[0]) <= 1:
        gs.add(i)
        gs.add(i+M)
    for j in range(M):
        l = L[j]
        if r[1] == l[0]:
            G[j+M].add((i, r[2]))
        if r[0] == l[1]:
            G[i].add((M+j, l[2]))

vs = set()
#print(dfs(12))
#print("st")
#print(gs)
RR = 10**18
for s in starts:
    vs.add(s)
    cc = R[s][2]
    f, A = dfs(s)
#    print("c",s)
    if f:
        RR = min(A+cc, RR)
#        print("R",A+cc)
#    print("c",s+M)
    f, A = dfs(s+M)
    if f:
        RR = min(A+cc, RR)
#        print(cc)
#        print("R",A+cc)
if RR == 10**18:
    print(-1)
else:
    print(RR)

Submission status: Wrong Answer

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

def dfs(v):
#    print("a",v,L[v-M] if v>=M else R[v])
    CC = 10**18
    ff = 0
    for u, c in G[v]:
        if u in vs:
            continue
        vs.add(u)
#        print(u)
        if u in gs:
            return 1, c
        f, c2 = dfs(u)
        if f:
            ff = 1
            CC = min(CC, c2+c)
    return ff, CC


N, = map(int, input().split())
R = []
L = []
for _ in range(N):
    s, c = input().split()
    t = s[::-1]
    c = int(c)
    for i in range(len(s)+1):
        R.append((s[i:], s[:i], c))
        L.append((t[i:], t[:i], c))
#print(R)
#print(L)
M = len(R)
G = [set() for _ in range(M*2)]
gs = set()
starts = list()
for i in range(M):
    r = R[i]
    if r[1] == "":
        starts.append(i)
    if len(r[0]) <= 1:
        gs.add(i)
        gs.add(i+M)
    for j in range(M):
        l = L[j]
        if r[1] == l[0]:
            G[j+M].add((i, r[2]))
        if r[0] == l[1]:
            G[i].add((M+j, l[2]))

vs = set()
#print(dfs(12))
#print("st")
#print(gs)
RR = 10**18
for s in starts:
    vs.add(s)
    cc = R[s][2]
    f, A = dfs(s)
#    print("c",s)
    if f:
        RR = min(A+cc, RR)
#        print("R",A+cc)
#    print("c",s+M)
    f, A = dfs(s+M)
    if f:
        RR = min(A+cc, RR)
#        print(cc)
#        print("R",A+cc)
if RR == 10**18:
    print(-1)
else:
    print(RR)

Submission status: Wrong Answer

Solution code:
mina=10**12
N=int(input())
L=list()
cost=list()
for i in range(N):
  S,C=input().split()
  C=int(C)
  for j in range(1,21):
    L.append(S*j)
    cost.append(C*j)
for i in range(N*20):
  S=L[i]
  C=cost[i]
  S=S[::-1]
  if S==L[i]:
    mina=min(mina,cost[i])
  for j in range(N*20):
    if L[j]==S:
      mina=min(mina,cost[j]+C)
    if L[j]==str(S[:-1]):
      mina=min(mina,cost[j]+C)
    if str(L[j][:-1])==S:
      mina=min(mina,cost[j]+C)
if mina==10**12:
  print(-1)
else:
  print(mina)

Submission status: Wrong Answer

Solution code:
mina=10**12
N=int(input())
L=list()
cost=list()
for i in range(N):
  S,C=input().split()
  C=int(C)
  for j in range(1,21):
    L.append(S*j)
    cost.append(C*j)
for i in range(N*20):
  S=L[i]
  C=cost[i]
  S=S[::-1]
  for j in range(N*20):
    if L[j]==S:
      mina=min(mina,cost[j]+C)
    if L[j]==str(S[:-1]):
      mina=min(mina,cost[j]+C)
    if str(L[j][:-1])==S:
      mina=min(mina,cost[j]+C)
if mina==10**12:
  print(-1)
else:
  print(mina)