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






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],0))
    nodes.add((word[:j+1],1))
    nodes.add((word[j:],0))
    nodes.add((word[j:],1))
    
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)

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],0))
    nodes.add((word[:j+1],1))
    nodes.add((word[j:],0))
    nodes.add((word[j:],1))
    
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)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import defaultdict
ns = defaultdict(set)
sc = [None]*n
nodes = []
for i in range(n):
    s,c = input().split()
    c = int(c)
    sc[i] = (s,c)
    nodes.extend([(0,s[i:]) for i in range(len(s))])
    nodes.extend([(1,s[:i]) for i in range(1, len(s)+1)])

for u in nodes:
    for s,c in sc:
        if u[0]==0 and s.endswith(u[1][::-1]):
            v = (1, s[:-len(u[1])])
            ns[u].add((c,v))
        elif u[0]==0 and u[1][::-1].endswith(s):
            v = (0, u[1][len(s):])
            ns[u].add((c,v))
        elif u[0]==1 and s.startswith(u[1][::-1]):
            v = (0, s[len(u[1]):])
            ns[u].add((c,v))
        elif u[0]==1 and u[1][::-1].startswith(s):
            v = (1, u[1][:-len(s)])
            ns[u].add((c,v))
start = 0
for s,c in sc:
    ns[start].add((c, (0,s)))
    ns[start].add((c, (1,s)))
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(start)
ans = float("inf")
for k,v in vals.items():
    if k==0:
        continue
    if k[1]==k[1][::-1]:
        ans = min(ans, v)
if ans==float("inf"):
    ans = -1
print(ans)

Solution (Python):
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 60
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
done = [set(), set()]
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if s in done[d]: continue
    done[d].add(s)
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Solution (Python):
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 60
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
done = [set(), set()]
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if s in done[d]: continue
    done[d].add(s)
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

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

main()

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



    
        
        

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

Solution (Python):
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 60
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
done = set()
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if r in done: continue
    done.add(r)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    lis = []
    c = []
    rev = []
    for _ in range(n):
        a,b = input().split()
        b = int(b)
        a = list(a)
        lis.append(a)
        rev.append(a[::-1])
        c.append(b)
    res = defaultdict(lambda : float("inf"))
    q = [(0,[],[])]
    res[(tuple(),tuple())] = 0
    while q:
        d,pre,suf = heappop(q)
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            print(d)
            return
        if len(pre) <= len(suf):
            k = suf[len(pre):]
            for i in range(n):
                s = lis[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    npre = pre+s
                    re = d+c[i]
                    i = tuple(npre)
                    j = tuple(suf)
                    if re < res[(i,j)]:
                        res[(i,j)] = re
                        heappush(q,(re,npre,suf))
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    nsuf = suf+s
                    re = d+c[i]
                    i = tuple(pre)
                    j = tuple(nsuf)
                    if re < res[(i,j)]:
                        res[(i,j)] = re
                        heappush(q,(re,pre,nsuf))
    print(-1)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 150
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from heapq import *

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8[:]), cache=True)
def main(S, C):
    N = len(C)
    INF = 1 << 60
    ind_l = np.where(S == -1)[0][:-1] + 1
    ind_r = np.where(S == -1)[0][1:]

    
    q = [(0, 0, 0, 0)] * 0
    for i in range(N):
        l, r = ind_l[i], ind_r[i]
        for n in range(0, r - l + 1):
            
            if np.all(S[l:l + n] == S[l:l + n][::-1]):
                
                heappush(q, (C[i], i, r - l - n, 0))
            
            if np.all(S[r - n:r] == S[r - n:r][::-1]):
                heappush(q, (C[i], i, r - l - n, 1))
    dist = np.full((50, 21, 2), INF, np.int64)
    for cost, i, n, pref_flag in q:
        dist[i, n, pref_flag] = cost

    while q:
        cost, i, n, pref_flag = heappop(q)
        if cost > dist[i, n, pref_flag]:
            continue
        if n == 0:
            
            return cost
        A = S[ind_l[i]:ind_r[i]]
        A = A[:n] if pref_flag else A[-n:]
        for j in range(N):
            B = S[ind_l[j]:ind_r[j]]
            match_len = min(n, len(B))

            if pref_flag:
                ok = np.all(A[-match_len:] == B[:match_len][::-1])
            else:
                ok = np.all(A[:match_len] == B[-match_len:][::-1])
            if not ok:
                continue
            if pref_flag:
                if n > match_len:
                    nxt = (cost + C[j], i, n - match_len, 1)
                else:
                    nxt = (cost + C[j], j, len(B) - match_len, 0)
            else:
                if n > match_len:
                    nxt = (cost + C[j], i, n - match_len, 0)
                else:
                    nxt = (cost + C[j], j, len(B) - match_len, 1)

            if dist[nxt[1], nxt[2], nxt[3]] <= nxt[0]:
                continue
            dist[nxt[1], nxt[2], nxt[3]] = nxt[0]
            heappush(q, nxt)
    return -1

N = int(readline())
S = []
C = []
for _ in range(N):
    w, c = readline().split()
    S.append(w)
    C.append(int(c))
S = np.array(list(b' '.join(S)), np.int64)
S[S == ord(' ')] = -1
S = np.insert(S, 0, -1)
S = np.append(S, -1)
C = np.array(C, np.int64)

print(main(S, C))