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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n = int(ipt())
    wrds = []
    hq = []
    usd = set()
    for i in range(n):
        s,c = input().split()
        c = int(c)
        wrds.append((s,c))
        hpq.heappush(hq,(c,s,1))

    while hq:
        hc,hs,hp = hpq.heappop(hq)
        usd.add((hs,hp))
        ls = len(hs)
        if hs == hs[::-1]:
            print(hc)
            exit()
        for si,ci in wrds:
            lsi = len(si)
            if lsi > ls:
                if hp == 1:
                    wt = si[::-1]
#                    print(wt)
                    if hs == wt[:ls:] and not (wt[ls::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,wt[ls::],-1))
                else:
                    if hs == si[:ls:] and not (si[ls::],1) in usd:
                        hpq.heappush(hq,(hc+ci,si[ls::],1))
            else:
                if hp == 1:
                    wt = si[::-1]
                    if wt == hs[:lsi:] and not (hs[lsi::],1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[lsi::],1))
                else:
                    if si == hs[:lsi:] and not (hs[lsi::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[ls::],-1))
#        print(hq)

    print(-1)


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n = int(ipt())
    wrds = []
    hq = []
    usd = set()
    for i in range(n):
        s,c = input().split()
        c = int(c)
        wrds.append((s,c))
        hpq.heappush(hq,(c,s,1))

    while hq:
        hc,hs,hp = hpq.heappop(hq)
        usd.add((hs,hp))
        ls = len(hs)
        if hs == hs[::-1]:
            print(hc)
            exit()
        for si,ci in wrds:
            lsi = len(si)
            if lsi > ls:
                if hp == 1:
                    wt = si[::-1]
#                    print(wt)
                    if hs == wt[:ls:] and not (wt[ls::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,wt[ls::],-1))
                else:
                    if hs == si[:ls:] and not (si[ls::],1) in usd:
                        hpq.heappush(hq,(hc+ci,si[ls::],1))
            else:
                if hp == 1:
                    wt = si[::-1]
                    if wt == hs[:lsi:] and not (hs[lsi::],1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[lsi::],1))
                else:
                    if si == hs[:lsi:] and not (hs[lsi::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[ls::],-1))
        print(hq)

    print(-1)


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n = int(ipt())
    wrds = []
    hq = []
    usd = set()
    for i in range(n):
        s,c = input().split()
        c = int(c)
        wrds.append((s,c))
        hpq.heappush(hq,(c,s,1))

    while hq:
        hc,hs,hp = hpq.heappop(hq)
#        print(hc,hs,hp)
        usd.add((hs,hp))
        ls = len(hs)
        if ls == 1 or ls == 0:
            print(hc)
            exit()
        for si,ci in wrds:
            if len(si) > ls:
                if hp == 1:
                    wt = si[::-1]
#                    print(wt)
                    if hs == wt[:ls:] and not (wt[ls::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,wt[ls::],-1))
                else:
                    if hs == si[:ls:] and not (si[ls::],1) in usd:
                        hpq.heappush(hq,(hc+ci,si[ls::],1))
            else:
                lsi = len(si)
                if hp == 1:
                    wt = si[::-1]
                    if wt == hs[:lsi:] and not (hs[lsi::],1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[lsi::],1))
                else:
                    if si == hs[:lsi:] and not (hs[lsi::],-1) in usd:
                        hpq.heappush(hq,(hc+ci,hs[ls::],-1))

    print(-1)


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        for lr in [0, 1]:
            heapq.heappush(q, (c, s, lr))


def check(st, ml):
    l = 0
    r = len(st) - 1
    while True:
        if l >= r:
            return ''
        if st[l] == st[r]:
            l += 1
            r -= 1
        else:
            break
    if l < ml:
        return 'X'
    return st[l:r + 1]


while q:
    c, s, lr = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        ml = min(len(s), len(s2))
        ns1 = check(s + s2 if lr == 0 else s2 + s, ml)
        if ns1 == 'X':
            continue
        elif ns1 == '':
            ans = min(ans, c + c2)
        elif ans > c + c2:
            if lr == 0 and len(s) > len(s2) or lr == 1 and len(s2) > len(s):
                nsr = 0
            else:
                nsr = 1
            heapq.heappush(q, (c + c2, ns1, nsr))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (c, s))


def check(st, ml):
    l = 0
    r = len(st) - 1
    while True:
        if l >= r:
            return ''
        if st[l] == st[r]:
            l += 1
            r -= 1
        else:
            break
    if l <= ml:
        return 'X'
    return st[l:r + 1]


while q:
    c, s = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        ml = min(len(s), len(s2))
        for ns in [s + s2, s2 + s]:
            ns1 = check(s + s2, ml)
            if ns1 == 'X':
                continue
            elif ns1 == '':
                ans = min(ans, c + c2)
            elif ans > c + c2:
                heapq.heappush(q, (c + c2, ns1))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (c, s))

while q:
    c, s = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1]:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s[len(s2):]))
            if s[::-1][:len(s2)] == s2:
                if s[::-1][len(s2):] == s[::-1][len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s[::-1][len(s2):]))
        else:
            if s2[:len(s)] == s[::-1]:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s2[len(s):]))
            if s2[::-1][:len(s)] == s:
                if s2[::-1][len(s):] == s2[::-1][len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s2[::-1][len(s):]))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def is_palindrome(S):
    d = deque(S)
    while d:
        if len(d) <= 1:
            return True
        if d[0] != d[-1]:
            return False
        d.popleft()
        d.pop()
    return True
def union(S1,S2):
    l1 = len(S1)
    l2 = len(S2)
    for i in range(min(l1,l2)):
        if S1[i] != S2[-i-1]:
            return (-1,'')
    if abs(l1-l2) <= 1:
        return (2,'')
    if l1 > l2:
        return (0,S1[l2:])
    else:
        return (1,S2[:l1+1])

N = int(input())
S = []
C = []
d = deque()
dic = {}
ans = 10**18
for i in range(N):
    Si,Ci = input().split()
    Ci = int(Ci)
    S.append(Si)
    C.append(Ci)
    if is_palindrome(Si):
        ans = min(ans,Ci)
    else:
        d.append((Ci,Si,0))
        d.append((Ci,Si,1))
        dic[(Si,0)] = Ci
        dic[(Si,1)] = Ci
while d:
    cost,string,order = d.popleft()
    for i in range(N):
        if order == 0:
            x,y = union(string,S[i])
        else:
            x,y = union(S[i],string)
        if x == -1:
            continue
        if is_palindrome(y):
            ans = min(ans,cost+C[i])
        else:
            if (y,x) in dic.keys():
                if dic[(y,x)] > cost+C[i]:
                    d.append((cost+C[i],y,x))
                    dic[(y,x)] = cost+C[i]
            else:
                d.append((cost+C[i],y,x))
                dic[(y,x)] = cost+C[i]
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (c, s))

while q:
    c, s = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1]:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s[len(s2):]))
            elif s[::-1][:len(s2)] == s2:
                if s[::-1][len(s2):] == s[::-1][len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s[::-1][len(s2):]))
        else:
            if s2[:len(s)] == s[::-1]:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s2[len(s):]))
            elif s2[::-1][:len(s)] == s:
                if s2[::-1][len(s):] == s2[::-1][len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s2[::-1][len(s):]))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def is_palindrome(S):
    d = deque(S)
    while d:
        if len(d) <= 1:
            return True
        if d[0] != d[-1]:
            return False
        d.popleft()
        d.pop()
    return True
def union(S1,S2):
    l1 = len(S1)
    l2 = len(S2)
    for i in range(min(l1,l2)):
        if S1[i] != S2[-i-1]:
            return (-1,'')
    if abs(l1-l2) <= 1:
        return (2,'')
    if l1 > l2:
        return (0,S1[l2:])
    else:
        return (1,S2[:l1])

N = int(input())
S = []
C = []
d = deque()
dic = {}
ans = 10**18
for i in range(N):
    Si,Ci = input().split()
    Ci = int(Ci)
    S.append(Si)
    C.append(Ci)
    if is_palindrome(Si):
        ans = min(ans,Ci)
    else:
        d.append((Ci,Si,0))
        d.append((Ci,Si,1))
        dic[(Si,0)] = Ci
        dic[(Si,1)] = Ci
while d:
    cost,string,order = d.popleft()
    for i in range(N):
        if order == 0:
            x,y = union(string,S[i])
        else:
            x,y = union(S[i],string)
        if x == -1:
            continue
        if is_palindrome(y):
            ans = min(ans,cost+C[i])
        else:
            if (y,x) in dic.keys():
                if dic[(y,x)] > cost+C[i]:
                    d.append((cost+C[i],y,x))
                    dic[(y,x)] = cost+C[i]
            else:
                d.append((cost+C[i],y,x))
                dic[(y,x)] = cost+C[i]
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (c, s))

while q:
    c, s = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1] or s[::-1][:len(s2)] == s2:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s[len(s2):]))
        else:
            if s2[:len(s)] == s[::-1] or s2[::-1][:len(s)] == s:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (c + c2, s2[len(s):]))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (s, c))

while q:
    s, c = heapq.heappop(q)
    if ans <= c:
        continue
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1] or s[::-1][:len(s2)] == s2:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (s[len(s2):], c + c2))
        else:
            if s2[:len(s)] == s[::-1] or s2[::-1][:len(s)] == s:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (s2[len(s):], c + c2))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (s, c))

while q:
    s, c = heapq.heappop(q)
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1] or s[::-1][:len(s2)] == s2:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (s[len(s2):], c + c2))
        else:
            if s2[:len(s)] == s[::-1] or s2[::-1][:len(s)] == s:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    if ans > c + c2:
                        heapq.heappush(q, (s2[len(s):], c + c2))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (s, c))

while q:
    s, c = heapq.heappop(q)
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1] or s[::-1][:len(s2)] == s2:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    heapq.heappush(q, (s[len(s2):], c + c2))
        else:
            if s2[:len(s)] == s[::-1] or s2[::-1][:len(s)] == s:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    heapq.heappush(q, (s2[len(s):], c + c2))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
sc = []
for _ in range(n):
    si, ci = input().split()
    sc.append((si, int(ci)))

q = []
ans = 100000000000000
for s, c in sc:
    if s == s[::-1]:
        ans = min(ans, c)
    else:
        heapq.heappush(q, (s, c))

while q:
    s, c = heapq.heappop(q)
    for s2, c2 in sc:
        if len(s) >= len(s2):
            if s[:len(s2)] == s2[::-1]:
                if s[len(s2):] == s[len(s2):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    heapq.heappush(q, (s[len(s2):], c + c2))
        else:
            if s2[::-1][:len(s)] == s:
                if s2[len(s):] == s2[len(s):][::-1]:
                    ans = min(ans, c + c2)
                else:
                    heapq.heappush(q, (s2[len(s):], c + c2))

print(-1 if ans == 100000000000000 else ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def is_palindrome(S):
    d = deque(S)
    while d:
        if len(d) <= 1:
            return True
        if d[0] != d[-1]:
            return False
        d.popleft()
        d.pop()
    return True
def union(S1,S2):
    l1 = len(S1)
    l2 = len(S2)
    for i in range(min(l1,l2)):
        if S1[i] != S2[-i-1]:
            return (-1,'')
    if abs(l1-l2) <= 1:
        return (2,'')
    if l1 > l2:
        return (0,S1[l2:])
    else:
        return (1,S2[:l1])

N = int(input())
S = []
C = []
d = deque()
dic = {}
ans = 10**18
for i in range(N):
    Si,Ci = input().split()
    Ci = int(Ci)
    S.append(Si)
    C.append(Ci)
    if is_palindrome(Si):
        ans = min(ans,Ci)
    else:
        d.append((Ci,Si,0))
        d.append((Ci,Si,1))
        dic[(Si,0)] = Ci
        dic[(Si,1)] = Ci
while d:
    cost,string,order = d.popleft()
    for i in range(N):
        if order == 0:
            x,y = union(string,S[i])
        else:
            x,y = union(S[i],string)
        if x == -1:
            continue
        if is_palindrome(y):
            ans = min(ans,cost+C[i])
        else:
            if (y,x) in dic:
                if dic[(y,x)] > cost+C[i]:
                    d.append((cost+C[i],y,x))
                    dic[(y,x)] = cost+C[i]
            else:
                d.append((cost+C[i],y,x))
                dic[(y,x)] = cost+C[i]
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def union(S1,S2):
    l1 = len(S1)
    l2 = len(S2)
    for i in range(min(l1,l2)):
        if S1[i] != S2[-i-1]:
            return (-1,-1)
    if abs(l1-l2) <= 1:
        return (2,0)
    if l1 > l2:
        return (0,S1[l2:])
    else:
        return (1,S2[:l1])
N = int(input())
S = []
C = []
d = deque()
dic = {}
ans = 10**18
for i in range(N):
    Si,Ci = input().split()
    Ci = int(Ci)
    S.append(Si)
    C.append(Ci)
    d.append((Ci,Si,0))
    d.append((Ci,Si,1))
    dic[(Si,0)] = Ci
    dic[(Si,1)] = Ci
while d:
    cost,string,order = d.popleft()
    for i in range(N):
        if order == 0:
            x,y = union(string,S[i])
        else:
            x,y = union(S[i],string)
        if x == -1:
            continue
        if not y:
            ans = min(ans,cost+C[i])
        else:
            if (y,x) in dic:
                if dic[(y,x)] > cost+C[i]:
                    d.append((cost+C[i],y,x))
                    dic[(y,x)] = cost+C[i]
            else:
                d.append((cost+C[i],y,x))
                dic[(y,x)] = cost+C[i]
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
def union(S1,S2):
    l1 = len(S1)
    l2 = len(S2)
    for i in range(min(l1,l2)):
        if S1[i] != S2[-i-1]:
            return (-1,-1)
    if abs(l1-l2) <= 1:
        return (2,0)
    if l1 > l2:
        return (0,S1[l2:])
    else:
        return (1,S2[:l1])
N = int(input())
S = []
C = []
d = deque()
ans = 10**18
for i in range(N):
    Si,Ci = input().split()
    Ci = int(Ci)
    S.append(Si)
    C.append(Ci)
    d.append((Ci,Si,0))
    d.append((Ci,Si,1))
while d:
    cost,string,order = d.popleft()
    for i in range(N):
        if order == 0:
            x,y = union(string,S[i])
        else:
            x,y = union(S[i],string)
        if x == -1:
            continue
        if not y:
            ans = min(ans,cost+C[i])
        else:
            d.append((cost+C[i],y,x))
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys

def input():
	return sys.stdin.readline()[:-1]

def is_palindrome(x):
	m = len(x)
	for i in range(m//2):
		if x[i] != x[m-1-i]:
			return False
	return True

INF = 10**18
n = int(input())
adj = defaultdict(set)
dp = defaultdict(lambda: INF)
dp["S"] = 0
#start: "S", goal: "T"
S = []
T = []
for _ in range(n):
	s, c = input().split()
	c = int(c)
	S.append((s, c))
	T.append((s[::-1], c))
	adj["S"].add((s, c))

for s, _ in S:
	for y in range(1, len(s)+1):
		pre = s[:y]
		if is_palindrome(pre):
			adj[pre].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if pre[-len(t):] == t:
						adj[pre].add((pre[:-len(t)], c))
				elif y < len(t):
					if pre == t[-y:]:
						adj[pre].add((t[:-y][::-1], c))
				else:
					if pre == t:
						adj[pre].add(("T", c))

		suf = s[-y:]
		if is_palindrome(suf):
			adj[suf].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if suf[:len(t)] == t:
						adj[suf].add((suf[len(t):], c))
				elif y < len(t):
					if suf == t[:y]:
						adj[suf].add((t[y:][::-1], c))
				else:
					if suf == t:
						adj[suf].add(("T", c))

que = [(0, "S")]
while que:
	tmp, s = heappop(que)
	if s == "T":
		print(tmp)
		sys.exit()
	"""
	if dp[s] < tmp:
		continue
	"""
	dp[s] = tmp
	for t, c in adj[s]:
		if dp[t] > tmp+c:
			heappush(que, (tmp+c, t))

if que:
	print(que[0][0])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys

def input():
	return sys.stdin.readline()[:-1]

def is_palindrome(x):
	m = len(x)
	for i in range(m//2):
		if x[i] != x[m-1-i]:
			return False
	return True

INF = 10**18
n = int(input())
adj = defaultdict(set)
dp = defaultdict(lambda: INF)
dp["S"] = 0
#start: "S", goal: "T"
S = []
T = []
for _ in range(n):
	s, c = input().split()
	c = int(c)
	S.append((s, c))
	T.append((s[::-1], c))
	adj["S"].add((s, c))

for s, _ in S:
	for y in range(1, len(s)+1):
		pre = s[:y]
		if is_palindrome(pre):
			adj[pre].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if pre[-len(t):] == t:
						adj[pre].add((pre[:-len(t)], c))
				elif y < len(t):
					if pre == t[-y:]:
						adj[pre].add((t[:-y][::-1], c))
				else:
					if pre == t:
						adj[pre].add(("T", c))

		suf = s[-y:]
		if is_palindrome(suf):
			adj[suf].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if suf[:len(t)] == t:
						adj[suf].add((suf[len(t):], c))
				elif y < len(t):
					if suf == t[:y]:
						adj[suf].add((t[y:][::-1], c))
				else:
					if suf == t:
						adj[suf].add(("T", c))

que = [(0, "S")]
while que:
	tmp, s = heappop(que)
	if dp[s] < tmp:
		continue
	dp[s] = tmp
	for t, c in adj[s]:
		if t == "T":
			print(tmp+c)
			sys.exit()
		if dp[t] > tmp+c:
			heappush(que, (tmp+c, t))

print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys

def input():
	return sys.stdin.readline()[:-1]

def is_palindrome(x):
	m = len(x)
	for i in range(m//2):
		if x[i] != x[m-1-i]:
			return False
	return True

INF = 10**18
n = int(input())
adj = defaultdict(set)
dp = defaultdict(lambda: INF)
dp["S"] = 0
#start: "S", goal: "T"
S = []
T = []
for _ in range(n):
	s, c = input().split()
	c = int(c)
	S.append((s, c))
	T.append((s[::-1], c))
	adj["S"].add((s, c))

for s, _ in S:
	for y in range(1, len(s)+1):
		pre = s[:y]
		if is_palindrome(pre):
			adj[pre].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if pre[-len(t):] == t:
						adj[pre].add((pre[:-len(t)], c))
				elif y < len(t):
					if pre == t[-y:]:
						adj[pre].add((t[:-y][::-1], c))
				else:
					if pre == t:
						adj[pre].add(("T", c))

		suf = s[-y:]
		if is_palindrome(suf):
			adj[suf].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if suf[:len(t)] == t:
						adj[suf].add((suf[len(t):], c))
				elif y < len(t):
					if suf == t[:y]:
						adj[suf].add((t[y:][::-1], c))
				else:
					if suf == t:
						adj[suf].add(("T", c))

que = [(0, "S")]
while que and que[0][1] != "T":
	tmp, s = heappop(que)
	if dp[s] < tmp:
		continue
	dp[s] = tmp
	for t, c in adj[s]:
		if dp[t] > tmp+c:
			heappush(que, (tmp+c, t))

if que:
	print(que[0][0])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys

def input():
	return sys.stdin.readline()[:-1]

def is_palindrome(x):
	m = len(x)
	for i in range(m//2):
		if x[i] != x[m-1-i]:
			return False
	return True

INF = 10**18
n = int(input())
adj = defaultdict(set)
dp = defaultdict(lambda: INF)
dp["S"] = 0
#start: "S", goal: "T"
S = []
T = []
for _ in range(n):
	s, c = input().split()
	c = int(c)
	S.append((s, c))
	T.append((s[::-1], c))
	adj["S"].add((s, c))

for s, _ in S:
	for y in range(1, len(s)+1):
		pre = s[:y]
		if is_palindrome(pre):
			adj[pre].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if pre[-len(t):] == t:
						adj[pre].add((pre[:-len(t)], c))
				elif y < len(t):
					if pre == t[-y:]:
						adj[pre].add((t[:-y][::-1], c))
				else:
					if pre == t:
						adj[pre].add(("T", c))

		suf = s[-y:]
		if is_palindrome(suf):
			adj[suf].add(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if suf[:len(t)] == t:
						adj[suf].add((suf[len(t):], c))
				elif y < len(t):
					if suf == t[:y]:
						adj[suf].add((t[y:][::-1], c))
				else:
					if suf == t:
						adj[suf].add(("T", c))

que = [(0, "S")]
while que and que[0][1] != "T":
	tmp, s = heappop(que)
	dp[s] = tmp
	for t, c in adj[s]:
		if dp[t] > tmp+c:
			heappush(que, (tmp+c, t))

if que:
	print(que[0][0])
else:
	print(-1)