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:
# -*- 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],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)

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],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)))
#print(graph)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

    # (cost, 文字列番号、文字数、perfix or suffix)
    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):
            # 左から n 文字が回文
            if np.all(S[l:l + n] == S[l:l + n][::-1]):
                # うしろ r - l - n 文字が余る
                heappush(q, (C[i], i, r - l - n, 0))
            # 右から n 文字が回文
            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))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
ss = []
cs = []
for i in range(n):
    s, c = stdin.readline().split()
    ss.append(s)
    cs.append(int(c))

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

ans = 999999999999999

while True:
    dpp = defaultdict(lambda: 999999999999999)
    rdpp = defaultdict(lambda: 999999999999999)
    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, 99999999999999):
                        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, 99999999999999):
                        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, 999999999999999):
                        rdpp[ns] = min(rdpp[ns], v + cs[p])
                elif s.startswith(k):
                    ns = s[len(k):]
                    if v + cs[p] < dp.get(ns, 999999999999999):
                        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 < 999999999999999 else -1)

Submission status: Runtime Error

Solution code:
import heapq

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

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

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

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

Submission status: Runtime Error

Solution code:
import heapq

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

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

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

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