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: Wrong Answer

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(1, 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: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys

def input():
	return sys.stdin.readline()[:-1]

def is_palindrome(x):
	m = len(x)
	for i in range(m//2):
		if x[i] != x[m-1-i]:
			return False
	return True

INF = 10**18
n = int(input())
adj = defaultdict(list)
dp = defaultdict(lambda: INF)
dp["S"] = 0
#start: "S", goal: "T"
S = []
T = []
for _ in range(n):
	s, c = input().split()
	c = int(c)
	S.append((s, c))
	T.append((s[::-1], c))
	adj["S"].append((s, c))

for s, _ in S:
	for y in range(1, len(s)+1):
		pre = s[:y]
		if is_palindrome(pre):
			adj[pre].append(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if pre[-len(t):] == t:
						adj[pre].append((pre[:-len(t)], c))
				elif y < len(t):
					if pre == t[-y:]:
						adj[pre].append((t[:-y][::-1], c))
				else:
					if pre == t:
						adj[pre].append(("T", c))

		suf = s[-y:]
		if is_palindrome(suf):
			adj[suf].append(("T", 0))
		else:
			for t, c in T:
				if y > len(t):
					if suf[:len(t)] == t:
						adj[suf].append((suf[len(t):], c))
				elif y < len(t):
					if suf == t[:y]:
						adj[suf].append((t[y:][::-1], c))
				else:
					if suf == t:
						adj[suf].append(("T", c))

que = [(0, "S")]
while que and que[0][1] != "T":
	tmp, s = heappop(que)
	dp[s] = tmp
	for t, c in adj[s]:
		if dp[t] > tmp+c:
			heappush(que, (tmp+c, t))

if que:
	print(que[0][0])
else:
	print(-1)

Submission status: Time Limit Exceeded

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

INF = 1 << 50

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

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



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

    min_val = INF
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False
        while queue:
            #print(queue)
            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()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    return min(cost, INF)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**9)
from collections import defaultdict
inf = 10**18

def main():
    N = int(input())
    S1 = []
    S2 = []
    C = []
    for i in range(N):
        s,c = input().split()
        S1.append(s)
        S2.append(s[::-1])
        C.append(int(c))
        
    d_l = defaultdict(lambda:inf)
    def left(s1):
        res = inf-1
        if s1==s1[::-1]:
            return 0
        if d_l[s1] != inf:
            return d_l[s1]
        for i in range(N):
            s2 = S2[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_l[s1] = res
        return res

    d_r = defaultdict(lambda:inf)
    def right(s2):
        res = inf-1
        if s2==s2[::-1]:
            return 0
        if d_r[s2] != inf:
            return d_r[s2]
        for i in range(N):
            s1 = S1[i]
            c = C[i]
            if s1.startswith(s2):
                res = min(res,left(s1[len(s2):])+c)
            if s2.startswith(s1):
                res = min(res,right(s2[len(s1):])+c)
        d_r[s2] = res
        return res

    ans = inf
    for i in range(N):
        ans = min(ans,left(S1[i])+C[i])

    if ans == inf:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
inf = 10**18
N = int(input())
S = []
C = []
for i in range(N):
    s,c = input().split()
    S.append(s)
    C.append(int(c))

def left(s1):
    res = inf
    if s1==s1[::-1]:
        return 0
    for i in range(N):
        s2 = S[i][::-1]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

def right(s2):
    res = inf
    if s2==s2[::-1]:
        return 0
    for i in range(N):
        s1 = S[i]
        c = C[i]
        if s1.startswith(s2):
            res = min(res,left(s1[len(s2):])+c)
        if s2.startswith(s1):
            res = min(res,right(s2[len(s1):])+c)
    return res

ans = inf
for i in range(N):
    ans = min(ans,left(S[i])+C[i])

if ans == inf:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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():
    def dfs(pre, suf):
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[])
    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: Time Limit Exceeded

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():
    def dfs(pre, suf):
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[])
    res = defaultdict(lambda : float("inf"))
    q = [(0,[],[])]
    res[(None,None)] = 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: Time Limit Exceeded

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

def ispalindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            return False
    return True

def main():
    N = int(input())
    S = []
    R = []
    INF = 10**40
    for _ in range(N):
        s, cc = input().split()
        c = int(cc)
        S.append((s, c))
        R.append((s[::-1], c))
    def helper(h, t):
        if not h and not t:
            return 0
        m = INF
        if not h:
            if ispalindrome(t):
                return 0
            for s, c in S:
                if s.startswith(t):
                    k = helper(s[len(t):], '')
                    if k < 0:
                        continue
                    m = min(m, c + k)
                elif t.startswith(s):
                    k = helper('', t[len(s):])
                    if k < 0:
                        continue
                    m = min(m, c + k)
                else:
                    continue
        else:
            if ispalindrome(h):
                return 0
            for s, c in R:
                if s.startswith(h):
                    k = helper('', s[len(h):])
                    if k < 0:
                        continue
                    m = min(m, c + k)
                elif h.startswith(s):
                    k = helper(h[len(s):], '')
                    if k < 0:
                        continue
                    m = min(m, c + k)
                else:
                    continue
        if m == INF:
            return -1
        return m
    M = INF
    for s, c in S:
        k = helper(s, '')
        if k < 0:
            continue
        M = min(M, c + k)
    if M == INF:
        return -1
    return M

print(main())

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())

sys.setrecursionlimit(1000000)
lim=100
def solve():
    def dfs(pre, suf,nu):
        if nu >= lim:
            return float("inf")
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf,nu+1)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s,nu+1)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[],0)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())

sys.setrecursionlimit(1000000)
lim=10**3
def solve():
    def dfs(pre, suf,nu):
        if nu >= lim:
            return float("inf")
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf,nu+1)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s,nu+1)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[],0)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())

sys.setrecursionlimit(1000000)
lim=10**5
def solve():
    def dfs(pre, suf,nu):
        if nu >= lim:
            return float("inf")
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf,nu+1)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s,nu+1)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[],0)
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def I(): return int(sys.stdin.readline())

sys.setrecursionlimit(1000000)

def solve():
    def dfs(pre, suf):
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[])
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

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

Submission status: Time Limit Exceeded

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():
    def dfs(pre, suf):
        ns = pre+suf[::-1]
        if ns != [] and ns == ns[::-1]:
            return 0
        res = 0
        cos = float("inf")
        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]:
                    re = dfs(pre+s,suf)+c[i]
                    if re < cos:
                        cos = re
        else:
            k = pre[len(suf):]
            for i in range(n):
                s = rev[i]
                m = min(len(s),len(k))
                if k[:m] == s[:m]:
                    re = dfs(pre,suf+s)+c[i]
                    if re < cos:
                        cos = re
        return res+cos

    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)
    ans = dfs([],[])
    if ans == float("inf"):
        ans = -1
    print(ans)
    return

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

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

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]
#                    print(wt)
                    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(hq)

    print(-1)


    return None

if __name__ == '__main__':
    main()