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 .

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1


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]

                    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[lsi::],-1))


    print(-1)


    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
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 = [[] 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

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

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

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
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 = [[] 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

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

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

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
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 = [[] 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

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

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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):




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)

Solution (Python):
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)

Solution (Python):
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])
    
    

    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]
    
    

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

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

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

Solution (Python):
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):
	
	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())
	
	
	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():
		
		
		cost, (s, is_front) = open_list.get()
		
		
		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)
			
			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
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)









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

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)









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
            
            cost, (l, r) = heappop(queue)
            if palindrome(l[0], r[0]):
                done = True
                
                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()

Solution (Python):
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)]

    
    
    string_to_id = [[[0] * (length[i] + 1) for i in range(N)] for _ in range(2)]
    id_to_string = {}  
    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
    
    
    

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


    
    
    min_cost = [10**18] * n
    q = []  
    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))
    

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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



def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





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)