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: Accepted

Solution code:
from heapq import heapify, heappop, heappush


def rolling(s):
    """
    文字列 [i, j] のハッシュ
    j < i の場合は逆順
    """
    n = len(s)
    ret = [[0] * n for _ in range(n)]

    for i in range(n):
        rh = 0
        for j in range(i, n):
            b = ord(s[j]) - 96
            rh = rh * 27 + b
            ret[i][j] = rh

    for j in range(n):
        rh = 0
        for i in range(j, -1, -1):
            b = ord(s[i]) - 96
            rh = rh * 27 + b
            ret[j][i] = rh

    return ret


def solve(n, sss, ccc, rhs):
    INF = 10 ** 18
    ans = INF
    q = []
    for i in range(n):
        s = sss[i]
        c = ccc[i]
        l = len(s)

        q.append((c, 0, i, 0))
        q.append((c, 1, i, l - 1))

        for j in range(l):
            k = 1
            while j - k >= 0 and j + k < l:
                if s[j - k] != s[j + k]:
                    break
                k += 1
            else:
                if j - k == -1 and j + k == l:
                    ans = min(ans, c)
                elif j - k == -1:
                    q.append((c, 0, i, j + k))
                else:
                    q.append((c, 1, i, j - k))

        for j in range(l - 1):
            k = 0
            while j - k >= 0 and j + k + 1 < l:
                if s[j - k] != s[j + k + 1]:
                    break
                k += 1
            else:
                if j - k == -1 and j + k + 1 == l:
                    ans = min(ans, c)
                elif j - k == -1:
                    q.append((c, 0, i, j + k + 1))
                else:
                    q.append((c, 1, i, j - k))

    heapify(q)

    checked = []
    for s in sss:
        checked.append([[False, False] for _ in range(len(s))])

    while q:
        cost, fb, i, j = heappop(q)
        if cost >= ans:
            break
        if checked[i][j][fb]:
            continue
        s = sss[i]
        ls = len(s)
        lm = ls - j if fb == 0 else j + 1
        checked[i][j][fb] = True
        rhr = rhs[i][j]

        if fb == 0:
            for ti in range(n):
                t = sss[ti]
                lt = len(t)
                if lm == lt:
                    if rhs[ti][-1][0] == rhr[-1]:
                        ans = min(ans, cost + ccc[ti])
                elif lm > lt:
                    if rhs[ti][-1][0] == rhr[j + lt - 1]:
                        heappush(q, (cost + ccc[ti], 0, i, j + lt))
                else:
                    if rhs[ti][-1][lt - lm] == rhr[-1]:
                        heappush(q, (cost + ccc[ti], 1, ti, lt - lm - 1))
        else:
            for ti in range(n):
                t = sss[ti]
                lt = len(t)
                if lm == lt:
                    if rhs[ti][0][-1] == rhr[0]:
                        ans = min(ans, cost + ccc[ti])
                elif lm > lt:
                    if rhs[ti][0][-1] == rhr[j - lt + 1]:
                        heappush(q, (cost + ccc[ti], 1, i, j - lt))
                else:
                    if rhs[ti][0][lm - 1] == rhr[0]:
                        heappush(q, (cost + ccc[ti], 0, ti, lm))

    if ans == INF:
        return -1
    else:
        return ans


n = int(input())
sss = []
ccc = []
rhs = []
for si in range(n):
    s, c = input().split()
    sss.append(s)
    ccc.append(int(c))
    rhs.append(rolling(s))

print(solve(n, sss, ccc, rhs))

Submission status: Accepted

Solution code:
from collections import deque


def isPalindrome(s):
    ''' s: string が回文か判定する. 回文 -> True, 回文でない -> False.
    '''
    L = len(s)
    return all(s[i] == s[L - 1 - i] for i in range(L // 2))


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

path = [dict() for _ in range(2)]  # 余り文字列へ到達するコスト, path[0]:左側余り, path[1]: 右側余り
q = deque()
S.sort(key=lambda x: x[1])  # コストの小さい順にソートしておくと速くなる.
# 初期処理. Siを左側余り文字列と見做してキューに入れていく.
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))

INF = 10 ** 15
ans = INF
while q:
    side, s0, c0 = q.popleft()

    if isPalindrome(s0):  # 余り文字列自体が回文のとき
        ans = min(ans, c0)
    else:  # 余り文字列が回文でないとき, 他の文字列を追加する
        for s1, c1 in S:
            if side == 0:
                l, r = s0, s1
            else:
                l, r = s1, s0

            L = len(l)
            R = len(r)
            isCandidate = False  # s1が追加可能な文字列かどうかを示すフラグ
            if L > R:
                if all(l[i] == r[-1 - i] for i in range(R)):
                    ns = l[R:]
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            elif L < R:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = r[:-L]
                    nc = c0 + c1
                    nside = 1
                    isCandidate |= True
            else:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = ''
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
                path[nside][ns] = nc
                q.append((nside, ns, nc))
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def isPalindrome(s):
    L = len(s)
    return all(s[i] == s[L - 1 - i] for i in range(L // 2))


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))

INF = 10 ** 15
ans = INF
while q:
    side, s0, c0 = q.popleft()
    if isPalindrome(s0):
        ans = min(ans, c0)
    else:
        for s1, c1 in S:
            if side == 0:
                l, r = s0, s1
            else:
                l, r = s1, s0

            L = len(l)
            R = len(r)
            isCandidate = False
            if L > R:
                if all(l[i] == r[-1 - i] for i in range(R)):
                    ns = l[len(r):]
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            elif L < R:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = r[:-len(l)]
                    nc = c0 + c1
                    nside = 1
                    isCandidate |= True
            else:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = ''
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
                path[nside][ns] = nc
                q.append((nside, ns, nc))
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque


def isPalindrome(s):
    L = len(s)
    return all(s[i] == s[L - 1 - i] for i in range(L // 2))


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))

INF = 10 ** 15
ans = INF
while q:
    side, s0, c0 = q.popleft()
    if isPalindrome(s0):
        ans = min(ans, c0)
    else:
        for s1, c1 in S:
            if side == 0:
                l, r = s0, s1
            else:
                l, r = s1, s0

            L = len(l)
            R = len(r)
            isCandidate = False
            if L > R:
                if all(l[i] == r[-1 - i] for i in range(R)):
                    ns = l[len(r):]
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            elif L < R:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = r[:-len(l)]
                    nc = c0 + c1
                    nside = 1
                    isCandidate |= True
            else:
                if all(l[i] == r[-1 - i] for i in range(L)):
                    ns = ''
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
                path[nside][ns] = nc
                q.append((nside, ns, nc))
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**12
LIM = 20
N = int(input())
D = dict()
for _ in range(N):
    s, c = input().split()
    if s in D.keys():
        D[s] = min(D[s], int(c))
    else:
        D[s] = int(c)

def check_kaibun(s):
    n = len(s)
    return all(s[i] == s[-i-1] for i in range(n//2))

def calc_cost(use):
    return sum(D[s] * n for (s, n) in use.items())

def find_candidate(cost, use, s, is_left):
    if check_kaibun(s):
        return min(cost, calc_cost(use))

    if is_left:
        for t in D.keys():
            # reversed s is included in the end of t
            if t[::-1].find(s) == 0:
                use[t] += 1
                if use[t] > LIM:
                    return INF
                c = find_candidate(cost, use, t[:-len(s):], False)
                cost = min(cost, c)
                use[t] -= 1
            # reveresed t is included in the begin of s
            elif s.find(t[::-1]) == 0:
                use[t] += 1
                c = find_candidate(cost, use, s[len(t):], True)
                cost = min(cost, c)
                use[t] -= 1
    else:
        for t in D.keys():
            # t is included in the end of reversed s
            if s[::-1].find(t) == 0:
                use[t] += 1
                c = find_candidate(cost, use, s[:-len(t):], False)
                cost = min(cost, c)
                use[t] -= 1
            # s is included in the begin of reveresed t
            elif t.find(s[::-1]) == 0:
                use[t] += 1
                c = find_candidate(cost, use, t[len(s):], True)
                cost = min(cost, c)
                use[t] -= 1

    return min(cost, INF)

def solve():
    ans = INF
    for s in D.keys():
        use = {s: 0 for s in D.keys()}
        use[s] = 1
        ans = find_candidate(ans, use, s, True)
    return ans if ans < INF else -1

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, start):
        import heapq
        que = []
        d = [float("inf")] * self.V

        for s in start:
            d[s]=0
            heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

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

node=[(0,""),(1,"")]
for s,c in string:
    for j in range(len(s)):
        node.append((0,s[j:]))
    for j in range(len(s)-1,-1,-1):
        node.append((1,s[:j+1]))

node=list(set(node))

iddata={i:e for e,i in enumerate(node)}
n=len(iddata)
edge=[[] for i in range(n)]
for i in range(n):
    if node[i][0]==0:
        S=node[i][1]
        for s,c in string:
            if len(s)<=len(S):
                check=all(S[j]==s[-j-1] for j in range(len(s)))
                if check:
                    if len(s)==len(S):
                        next_node=(0,"")
                    else:
                        next_node=(0,S[len(s):])
                    next_id=iddata[next_node]
                    edge[i].append((next_id,c))
            else:
                check=all(S[j]==s[-j-1] for j in range(len(S)))
                if check:
                    if len(s)==len(S):
                        next_node=(1,"")
                    else:
                        next_node=(1,s[:len(s)-len(S)])
                    next_id=iddata[next_node]
                    edge[i].append((next_id,c))
    else:
        S=node[i][1]
        for s,c in string:
            if len(s)<=len(S):
                check=all(s[j]==S[-j-1] for j in range(len(s)))
                if check:
                    if len(s)==len(S):
                        next_node=(1,"")
                    else:
                        next_node=(1,S[:len(S)-len(s)])
                    next_id=iddata[next_node]
                    edge[i].append((next_id,c))
            else:
                check=all(s[j]==S[-j-1] for j in range(len(S)))
                if check:
                    if len(s)==len(S):
                        next_node=(0,"")
                    else:
                        next_node=(0,s[len(S):])
                    next_id=iddata[next_node]
                    edge[i].append((next_id,c))

palindrome=Dijkstra(n+1)
for i in range(n):
    for j,c in edge[i]:
        palindrome.add(j,i,c)

start=[]
for i in range(n):
    s=node[i][1]
    if len(s)==0:
        start.append(i)
    else:
        check=all(s[j]==s[-1-j] for j in range(len(s)))
        if check:
            start.append(i)

for s,c in string:
    id=iddata[0,s]
    palindrome.add(id,n,c)
    id=iddata[1,s]
    palindrome.add(id,n,c)

res=palindrome.shortest_path(start)
ans=res[n]

#print(list(map(lambda x:node[x],start)))
#for i in range(n):
    #if node[i][1]=="abc":
        #print(node[i])
        #print(list(map(lambda x:(node[x[0]],x[1]),edge[i])))

if ans!=float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

            isCandidate = False
            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
                    nside = 0
                    isCandidate |= True
            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
                    nside = 1
                    isCandidate |= True
            else:
                for i in range(len(l)):
                    if l[i] != r[-1 - i]:
                        break
                else:
                    ns = ''
                    nc = c0 + c1
                    nside = 0
                    isCandidate |= True
            if isCandidate and (ns not in path[nside] or path[nside][ns] > nc):
                path[nside][ns] = nc
                q.append((nside, ns, nc))
if isPossible:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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) != 1 and node[1:]==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: Accepted

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: Accepted

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
                    flag=1
    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: Accepted

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
                    flag=1
    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)