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:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
from heapq import heappop, heappush
def resolve():
    n = int(input())
    S = [None] * n
    C = [None] * n
    for i in range(n):
        S[i], C[i] = input().split()
        C[i] = int(C[i])
    for i in range(n):
        S.append(S[i][::-1])
        C.append(C[i])

    # id[i][j] : index of S[i][j:]
    id = [[] for _ in range(2 * n)]
    N = 1
    for i in range(2 * n):
        for j in range(len(S[i])):
            id[i].append(N)
            N += 1

    # make graph
    E = [[] for _ in range(N)]
    for i, ni in product(range(2 * n), repeat = 2):
        if i // n == ni // n:
            continue
        for j in range(len(S[i])):
            now = S[i][j:]
            edge = S[ni]
            if not (now.startswith(edge) or edge.startswith(now)):
                continue
            if len(now) > len(edge):
                E[id[i][j]].append((id[i][j + len(edge)], C[ni]))
            elif len(now) < len(edge):
                E[id[i][j]].append((id[ni][len(now)], C[ni]))
            else:
                E[id[i][j]].append((0, C[ni]))

    # Dijkstra
    dist = [INF] * N
    queue = []
    for i, c in enumerate(C):
        dist[id[i][0]] = c
        heappush(queue, (c, id[i][0]))
    while queue:
        d, v = heappop(queue)
        if d != dist[v]:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(queue, (d + w, nv))

    ans = dist[0]
    for i in range(2 * n):
        for j in range(len(S[i])):
            T = S[i][j:]
            if T == T[::-1]:
                ans = min(ans, dist[id[i][j]])
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
from heapq import heappop, heappush
def resolve():
    n = int(input())
    S = [None] * n
    C = [None] * n
    for i in range(n):
        S[i], C[i] = input().split()
        C[i] = int(C[i])
    for i in range(n):
        S.append(S[i][::-1])
        C.append(C[i])

    # id[i][j] : index of S[i][j:]
    id = [[] for _ in range(2 * n)]
    N = 1
    for i in range(2 * n):
        for j in range(len(S[i])):
            id[i].append(N)
            N += 1

    # make graph
    E = [[] for _ in range(N)]
    for i, ni in product(range(2 * n), repeat = 2):
        if i // n == ni // n:
            continue
        for j in range(len(S[i])):
            now = S[i][j:]
            edge = S[ni]
            l = min(len(now), len(edge))
            if now[:l] != edge[:l]:
                continue
            nv = None
            if len(now) > len(edge):
                E[id[i][j]].append((id[i][j + len(edge)], C[ni]))
            elif len(now) < len(edge):
                E[id[i][j]].append((id[ni][len(now)], C[ni]))
            else:
                E[id[i][j]].append((0, C[ni]))

    # Dijkstra
    dist = [INF] * N
    queue = []
    for i, c in enumerate(C):
        dist[id[i][0]] = c
        heappush(queue, (c, id[i][0]))
    while queue:
        d, v = heappop(queue)
        if d != dist[v]:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(queue, (d + w, nv))

    ans = dist[0]
    for i in range(2 * n):
        for j in range(len(S[i])):
            T = S[i][j:]
            if T == T[::-1]:
                ans = min(ans, dist[id[i][j]])

    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
from heapq import heappop, heappush
def resolve():
    n = int(input())
    S = [None] * n
    C = [None] * n
    for i in range(n):
        S[i], C[i] = input().split()
        C[i] = int(C[i])
    for i in range(n):
        S.append(S[i][::-1])
        C.append(C[i])

    # id[i][j] : index of S[i][-j:]
    id = [[] for _ in range(2 * n)]
    N = 1
    for i in range(2 * n):
        for j in range(len(S[i])):
            id[i].append(N)
            N += 1

    # make graph
    E = [[] for _ in range(N)]
    for i, ni in product(range(2 * n), repeat = 2):
        if i // n == ni // n:
            continue
        for j in range(len(S[i])):
            now = S[i][j:]
            edge = S[ni]
            l = min(len(now), len(edge))
            if now[:l] != edge[:l]:
                continue
            c = C[ni]
            v = id[i][j]
            nv = None
            if len(now) > len(edge):
                E[id[i][j]].append((id[i][j + len(edge)], c))
            elif len(now) < len(edge):
                E[id[i][j]].append((id[ni][len(now)], c))
            else:
                E[id[i][j]].append((0, c))

    # Dijkstra
    dist = [INF] * N
    queue = []
    for i, c in enumerate(C):
        dist[id[i][0]] = c
        heappush(queue, (c, id[i][0]))
    while queue:
        d, v = heappop(queue)
        if d != dist[v]:
            continue
        for nv, w in E[v]:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                heappush(queue, (dist[nv], nv))

    ans = dist[0]
    for i in range(2 * n):
        for j in range(len(S[i])):
            T = S[i][j:]
            if T == T[::-1]:
                ans = min(ans, dist[id[i][j]])

    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    N = int(input())
    S = []
    R = []
    C = []
    for _ in range(N):
        s, c = input().strip().split()
        S.append(s)
        R.append(s[::-1])
        C.append(int(c))
    
    vis = set()
    mem = dict()

    def dp(s, p):
        if (s, p) in mem: return mem[s, p]
        if s == s[::-1]: return 0
        if (s, p) in vis: return INF

        ans = INF
        vis.add((s, p))
        for i, t in enumerate(S if p else R):
            if len(t) >= len(s) and t.startswith(s):
                ans = min(ans, dp(t[len(s):], p ^ 1) + C[i])
            elif len(s) > len(t) and s.startswith(t):
                ans = min(ans, dp(s[len(t):], p) + C[i])
        vis.discard((s, p))
        mem[s, p] = ans
        return ans
        
    ans = INF
    for i in range(N):
        ans = min(ans, dp(S[i], 0) + C[i])
    return -1 if ans == INF else ans


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Accepted

Solution code:
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    N = int(input())
    S = []
    C = []
    for _ in range(N):
        s, c = input().strip().split()
        S.append(s)
        C.append(int(c))
    
    vis = set()
    mem = dict()

    def dp(s, p):
        if (s, p) in mem:
            return mem[s, p]

        if s == s[::-1]:
            return 0

        if (s, p) in vis:
            return INF

        vis.add((s, p))

        ans = INF
        if p == 0:
            for i in range(N):
                if len(S[i]) >= len(s):
                    if S[i][::-1].startswith(s):
                        ans = min(ans, dp(S[i][:-len(s)], 1) + C[i])
                else:
                    if s.startswith(S[i][::-1]):
                        ans = min(ans, dp(s[len(S[i]):], 0) + C[i])
        else:
            for i in range(N):
                if len(S[i]) >= len(s):
                    if S[i].startswith(s[::-1]):
                        ans = min(ans, dp(S[i][len(s):], 0) + C[i])
                else:
                    if s[::-1].startswith(S[i]):
                        ans = min(ans, dp(s[:-len(S[i])], 1) + C[i])

        vis.discard((s, p))
        mem[s, p] = ans
        return ans
        
    ans = INF
    for i in range(N):
        ans = min(ans, dp(S[i], 0) + C[i])
    return -1 if ans == INF else ans


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#参考
#https://atcoder.jp/contests/abc175/submissions/15939709

import sys
from collections import defaultdict 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 10**31
N = int(readline())
ss = []
cs = []
for i in range(N):
    s, c = readline().decode().rstrip().split()
    ss.append(s)
    cs.append(int(c))
    
dp = defaultdict(lambda:INF)
rdp = defaultdict(lambda:INF)
p = 0

ved = set()
for s in ss:
    dp[s] = min(dp[s], cs[p])
    p += 1
    ved.add(s)

ans = INF

while True:
    dpp = defaultdict(lambda:INF)
    rdpp = defaultdict(lambda:INF)
    
    for k, v in dp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s[::-1]):
                    ns = k[len(s):]
                    if v + cs[p] < dp.get(ns,INF):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                elif s[::-1].startswith(k):
                    ns = s[::-1][len(k):]
                    if v + cs[p] < rdp.get(ns,INF):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                p += 1
     
    for k, v in rdp.items():
        if k == k[::-1]:
            ans = min(ans, v)
        else:
            p = 0
            for s in ss:
                if k.startswith(s):
                    ns = k[len(s):]
                    if v + cs[p] < rdp.get(ns,INF):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                elif s.startswith(k):
                    ns = s[len(k):]
                    if v + cs[p] < dp.get(ns,INF):
                        dpp[ns] = min(dpp[ns], v + cs[p])
                p += 1
    if len(dpp) + len(rdpp) == 0:
        break
    for k, v in dpp.items(): 
        dp[k] = v
    for k, v in rdpp.items(): 
        rdp[k] = v

print(ans if ans < INF else -1)

Submission status: Accepted

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

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    ll = set([""])
    rr = set()
    for s, c in sc:
        for i in range(len(s)):
            pre = s[:i + 1]
            suf = s[i:]
            ll.add(pre[::-1])
            rr.add(suf[::-1])
    #print(ll)
    #print(rr)

    ln = len(ll)
    rn = len(rr)
    ltou = {l: u for u, l in enumerate(ll)}
    rtou = {r: u + ln for u, r in enumerate(rr)}
    ispal = [False] * (ln + rn)
    for l, u in ltou.items(): ispal[u] = l == l[::-1]
    for r, u in rtou.items(): ispal[u] = r == r[::-1]
    #print("ltou", ltou)
    #print("rtou", rtou)

    to = [[] for _ in range(ln + rn)]
    for s, c in sc:
        c = int(c)
        for l in ll:
            u = ltou[l]
            v = -1
            if l == s: v = ltou[""]
            elif l[:len(s)] == s: v = ltou[l[len(s):]]
            elif l == s[:len(l)]: v = rtou[s[len(l):][::-1]]
            if v != -1: to[u].append((v, c))
        for r in rr:
            u = rtou[r]
            v = -1
            if r == s: v = ltou[""]
            elif r[-len(s):] == s: v = rtou[r[:-len(s)]]
            elif r == s[-len(r):]: v = ltou[s[:-len(r)][::-1]]
            if v != -1: to[u].append((v, c))
    #print(to)

    inf = 10 ** 16
    dist = [inf] * (ln + rn)
    hp = []
    for s, c in sc:
        u = rtou[s[::-1]]
        if dist[u]>int(c):
            heappush(hp, (int(c), u))
            dist[u] = int(c)
    while hp:
        d, u = heappop(hp)
        if d > dist[u]: continue
        for v, c in to[u]:
            if dist[v] <= d + c: continue
            dist[v] = d + c
            heappush(hp, (d + c, v))
    #print(dist)

    ans = min(dist[u] for u in range(ln + rn) if ispal[u])
    if ans == inf: print(-1)
    else: print(ans)

n = II()
sc = [SI().split() for _ in range(n)]
solve()

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def is_kaibun(s):
	if len(s) <= 1:
		return True
	for c, cc in zip(s,s[::-1]):
		if c != cc:
			return False
	return True
	
	
def mk_sub(s, other, s_is_front):
	#pa((s,other,s[:len(other)],other[:len(s)]))
	if len(s) <= len(other) and s == other[:len(s)]:
		return True, other[len(s):], not s_is_front
	elif len(s)>len(other) and s[:len(other)] == other:
		return True, s[len(other):], s_is_front
	return False, '', False

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	dd_f = {}
	dd_b = {}
	for _ in range(n):
		s, v = input().split()
		v = int(v)
		if s in dd_f:
			v = min(v, dd_f[s])
		dd_f[s] = v
		dd_b[s[::-1]]=v
	front=True
	open_list=queue.PriorityQueue()
	close_list_f = set()
	close_list_b = set()
	for k in dd_f:
		open_list.put((dd_f[k], (k, front)))
		
	while not open_list.empty():
		#pa('rrrr')
		#return 
		cost, (s, is_front) = open_list.get()
		#pa((cost,s,is_front))
		#pa(s if is_front else s[::-1])
		if is_kaibun(s):
			return cost
		if (is_front and s in close_list_f) or (not is_front and s in close_list_b):
			continue
		if is_front:
			close_list_f.add(s)
		else:
			close_list_b.add(s)
			
		dic = dd_b if is_front else dd_f
		for k in dic:
			is_ok, next_s, r_is_front=mk_sub(s, k, is_front)
			#pa((is_ok,next_s,r_is_front,k))
			if not is_ok:
				continue
			elif r_is_front and next_s in close_list_f:
				continue
			elif not r_is_front and next_s in close_list_b:
				continue
			else:
				open_list.put((cost + dic[k], (next_s, r_is_front)))
		
	return -1
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def search_next(l, r, SC):
    ll, lc = l
    rr, rc = r
    nexts = []
    if len(ll) > len(rr):
        part = ll[::-1]
        for s,c in SC:
            if s[-len(part):] == part:
                r_n = (s[:-len(ll)], rc + c)
                l_n = ('', lc)
                nexts.append((rc+c+lc, (l_n, r_n)))
            elif s == part[-len(s):]:
                l_n =(ll[len(s):], lc)
                r_n = ('', rc + c)
                nexts.append((rc + c + lc, (l_n, r_n)))
    else:
        part = rr[::-1]
        for s, c in SC:
            if s[:len(part)] == part:
                l_n = (s[len(rr):], lc + c)
                r_n = ('', rc)
                nexts.append((lc+rc+c, (l_n, r_n)))
            elif s == part[:len(s)]:
                r_n = (rr[:-len(s)], rc)
                l_n = ('', lc + c)
                nexts.append((lc + rc + c, (l_n, r_n)))
    return nexts

def palindrome(l, r):
    if l + r == (l+r)[::-1]:
        return True
    else:
        return False



def run():
    totalL = 0
    N = int(sysread())
    SC = []
    for i in range(N):
        s,c = input().split()
        c = int(c)
        SC.append((s,c))
        totalL += len(s)

    min_val = INF
    cache = set()
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False

        while queue:
            #print(queue)
            cost, (l, r) = heappop(queue)
            if (l[0], r[0]) in cache: continue
            cache.add((l[0], r[0]))
            if palindrome(l[0], r[0]):
                done = True
                #print(l, r)
                cache.remove((l[0], r[0]))
                break
            nexts = search_next(l, r, SC)
            for n in nexts:
                heappush(queue, n)
        if done:
            min_val = min(min_val, cost)
    if min_val == INF:
        print(-1)
    else:
        print(min_val)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def search_next(l, r, SC):
    ll, lc = l
    rr, rc = r
    nexts = []
    if len(ll) > len(rr):
        part = ll[::-1]
        for s,c in SC:
            if s[-len(part):] == part:
                r_n = (s[:-len(ll)], rc + c)
                l_n = ('', lc)
                nexts.append((rc+c+lc, (l_n, r_n)))
            elif s == part[-len(s):]:
                l_n =(ll[len(s):], lc)
                r_n = ('', rc + c)
                nexts.append((rc + c + lc, (l_n, r_n)))
    else:
        part = rr[::-1]
        for s, c in SC:
            if s[:len(part)] == part:
                l_n = (s[len(rr):], lc + c)
                r_n = ('', rc)
                nexts.append((lc+rc+c, (l_n, r_n)))
            elif s == part[:len(s)]:
                r_n = (rr[:-len(s)], rc)
                l_n = ('', lc + c)
                nexts.append((lc + rc + c, (l_n, r_n)))
    return nexts

def palindrome(l, r):
    if l + r == (l+r)[::-1]:
        return True
    else:
        return False



def run():
    totalL = 0
    N = int(sysread())
    SC = []
    for i in range(N):
        s,c = input().split()
        c = int(c)
        SC.append((s,c))
        totalL += len(s)

    min_val = INF
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False
        count = 0
        while queue:
            count += 1
            if count > 200000:break
            #print(queue)
            cost, (l, r) = heappop(queue)
            if palindrome(l[0], r[0]):
                done = True
                #print(l, r)
                break
            nexts = search_next(l, r, SC)
            for n in nexts:
                heappush(queue, n)
        if done:
            min_val = min(min_val, cost)
    if min_val == INF:
        print(-1)
    else:
        print(min_val)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    回文文字列を左右からそれぞれ構成していく。
    左の文字列と右の文字列のうち短い方に文字を足していく。
    例えば左に文字列をくっつけたとすると、一般に左側が数文字余る。
    この数文字が回文になっていれば全体も回文。
    そうでなければ左側の余り文字列を含むようないい文字列を右側にくっつければ良い。

    この手法だと回文が生成可能かどうかが多項式時間で判定可能。
    なぜなら左右を見て余る文字列はS1,...,SNのprefixないしsuffixに限定されるから。

    最後にコスト最小の回文をどう発見するかだが、これは余った文字列の状態を頂点とする
    グラフを構成してダイクストラをすれば良い。
    """
    N = int(input())
    string = []
    cost = []
    for _ in range(N):
        s, c = input().split()
        string.append(s)
        cost.append(int(c))
    length = [len(string[i]) for i in range(N)]

    # グラフ頂点の構成（余りなしの文字列の状態をn = 0番目とする）
    # string_to_id[d][i][j] = (Siの先頭(d=0)もしくは末尾(d=1)からj文字とった部分文字列)
    string_to_id = [[[0] * (length[i] + 1) for i in range(N)] for _ in range(2)]
    id_to_string = {}  # id_to_string[id] = (d, i, j)
    n = 1
    for d in range(2):
        for i in range(N):
            for j in range(1, length[i] + 1):
                string_to_id[d][i][j] = n
                id_to_string[n] = (d, i, j)
                n += 1
    #print("n={}".format(n))
    #print("string_to_id={}".format(string_to_id))
    #print("id_to_string={}".format(id_to_string))

    # グラフ辺の構成
    repn = [[] for _ in range(n)]
    for i in range(N):
        repn[0].append((string_to_id[0][i][length[i]], cost[i]))
        repn[0].append((string_to_id[1][i][length[i]], cost[i]))
    for v in range(1, n):
        d, i, j = id_to_string[v]
        if d == 0:
            # 先頭が余っている＝右の文字列が長い場合
            for ni in range(N):
                if j <= length[ni]:
                    # 左に文字列を追加して左側が長くなる場合
                    if string[ni][:j] != (string[i][:j])[::-1]: continue
                    id = string_to_id[1][ni][length[ni] - j]
                else:
                    # 左側に文字列を追加してもまだ右側が長い場合
                    if string[ni] != (string[i][(j - length[ni]):j])[::-1]: continue
                    id = string_to_id[0][i][j - length[ni]]
                repn[v].append((id, cost[ni]))
        else:
            # 末尾が余っている＝左の文字列が長い場合
            for ni in range(N):
                if j <= length[ni]:
                    # 右に文字列を追加して右側が長くなる場合
                    if (string[i][-j:])[::-1] != string[ni][-j:]: continue
                    id = string_to_id[0][ni][length[ni] - j]
                else:
                    # 右側に文字列を追加してもまだ左側が長い場合
                    if (string[i][-j:(-j + length[ni])])[::-1] != string[ni]: continue
                    id = string_to_id[1][i][j - length[ni]]
                repn[v].append((id, cost[ni]))
        #print("repn[{}]={}".format(v, repn[v]))


    # ダイクストラ（キューの中身は辺のコストじゃなくてそこまでの合計コストですよ！！！！！！）
    # あとキューに入れる時に距離を確定（「コスト最初距離候補」ではなく「距離確定の中の最小」から進めるから）
    min_cost = [10**18] * n
    q = []  # (qの中身)＝(dist, to)
    for v, cos in repn[0]:
        min_cost[v] = cos
        heappush(q, (cos, v))
    while q:
        dist, v = heappop(q)
        if min_cost[v] != dist: continue  # 枝刈り１回目
        for nv, ncos in repn[v]:
            if min_cost[nv] <= dist + ncos: continue  # 枝刈り２回目
            min_cost[nv] = dist + ncos
            heappush(q, (dist + ncos, nv))
    #for v in range(n): print("min_cost[{}]={}".format(v, min_cost[v]))

    # 最小コストを探索
    ans = 10**18
    ans = min(ans, min_cost[0])  # きれいに終わる場合を忘れてた
    for v in range(1, n):
        d, i, j = id_to_string[v]
        if d == 0:
            substring = string[i][:j]
        else:
            substring = string[i][-j:]
        if substring == substring[::-1]:
            ans = min(ans, min_cost[v])

    if ans == 10**18:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
data = SLL(N)
words = []
costs = []
nodes = {("",0),("",1)}

best = INF
for d in data:
  word = d[0]
  cost = int(d[1])
  if word == word[::-1]:
    best = min(best,cost)
    continue
  words.append(word)
  costs.append(cost)
  for j in range(len(word)):
    nodes.add((word[:j+1],1))
    nodes.add((word[j:],0))
    
graph = {k:[] for k in nodes}
graph[("",1)].append((0,("",0)))
for k in nodes:
  amari = k[0]
  t = k[1]
  if amari == amari[::-1]:
    if amari:
      graph[k].append((0,("",0)))
  else:
    n = len(amari)
    for i in range(len(words)):
      word = words[i]
      cost = costs[i]
      if t == 0:
        if len(word)>n:
          if amari == word[::-1][:n]:
            graph[k].append((cost,(word[:-n],1)))
        else:
          if amari[:len(word)] == word[::-1]:
            graph[k].append((cost,(amari[len(word):],0)))
      else:
        if len(word)>n:
          if amari[::-1] == word[:n]:
            graph[k].append((cost,(word[n:],0)))
        else:
          if amari[::-1][:len(word)] == word:
            graph[k].append((cost,(amari[:-len(word)],1)))

def dijkstra(graph, start,cost):
  N = len(graph)
  d = {k:INF for k in nodes}
  d[start] = cost
  f = {k:False for k in nodes}
  q = [(cost, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        heapq.heappush(q, (c + d[u], v))
  return d   

for i in range(len(words)):
  word = words[i]
  cost = costs[i]
  best = min(best,dijkstra(graph,(word,0),cost)[("",0)])
  best = min(best,dijkstra(graph,(word,1),cost)[("",0)])
  
if best == INF:
  print(-1)
else:
  print(best)