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

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

from heapq import *

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys

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

from heapq import *

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

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

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

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

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

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

Submission status: Wrong Answer

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

INF = 1 << 50

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

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



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

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

        while queue:
            #print(queue)
            cost, (l, r) = heappop(queue)
            if palindrome(l[0], r[0]):
                done = True
                #print(l, r)
                break
            if (l, r) in cache: break
            cache.add((l, r))
            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: Wrong Answer

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 = []
        cache = set()
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False

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

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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):
        for s,c in SC:
            l_n = (ll + s, lc + c)
            nexts.append((lc+c+rc, (l_n, r)))
    elif len(ll) > len(rr):
        part = ll[len(rr):][::-1]
        for s,c in SC:
            if s[-len(part):] == part or s in part:
                r_n = (s + rr, rc + c)
                nexts.append((rc+c+lc, (l, r_n)))
    else:
        part = rr[:-len(ll)][::-1]
        for s, c in SC:
            if s[:len(part)] == part or s in part:
                l_n = (ll + s, lc + c)
                nexts.append((lc+rc+c, (l_n, r)))
    return nexts

def palindrome(l, r):
    if len(l+r) > 1 and 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
            if len(l[0]) + len(r[0]) > totalL * 3:
                continue
            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: Wrong Answer

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):
        for s,c in SC:
            l_n = (ll + s, lc + c)
            nexts.append((lc+c+rc, (l_n, r)))
    elif len(ll) > len(rr):
        part = ll[len(rr):][::-1]
        for s,c in SC:
            if s[-len(part):] == part or s in part:
                r_n = (s + rr, rc + c)
                nexts.append((rc+c+lc, (l, r_n)))
    else:
        part = rr[:-len(ll)][::-1]
        for s, c in SC:
            if s[:len(part)] == part or s in part:
                l_n = (ll + s, lc + c)
                nexts.append((lc+rc+c, (l_n, r)))
    return nexts

def palindrome(l, r):
    if len(l+r) > 1 and 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
            if len(l[0]) + len(r[0]) > totalL:
                continue
            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: Wrong Answer

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):
        for s,c in SC:
            l_n = (ll + s, lc + c)
            nexts.append((lc+c+rc, (l_n, r)))
    elif len(ll) > len(rr):
        part = ll[len(rr):][::-1]
        for s,c in SC:
            if s[-len(part):] == part or s in part:
                r_n = (s + rr, rc + c)
                nexts.append((rc+c+lc, (l, r_n)))
    else:
        part = rr[:-len(ll)][::-1]
        for s, c in SC:
            if s[:len(part)] == part or s in part:
                l_n = (ll + s, lc + c)
                nexts.append((lc+rc+c, (l_n, r)))
    return nexts

def palindrome(l, r):
    if len(l+r) > 1 and 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
            if len(l[0]) + len(r[0]) > totalL * 2:
                continue
            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: Wrong Answer

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


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

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

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

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

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


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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

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

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

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

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


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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

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

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

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

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


    # ダイクストラ（キューの中身は辺のコストじゃなくてそこまでの合計コストですよ！！！！！！）
    min_cost = [10**18] * n
    q = []  # (qの中身)＝(dist, to)
    for v, cos in repn[0]: heappush(q, (cos, v))
    while q:
        dist, v = heappop(q)
        if min_cost[v] < dist: continue
        min_cost[v] = dist
        for nv, ncos in repn[v]:
            heappush(q, (dist + ncos, nv))
    #for v in range(n): print("min_cost[{}]={}".format(v, min_cost[v]))

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

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

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

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

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


    # ダイクストラ（キューの中身は辺のコストじゃなくてそこまでの合計コストですよ！！！！！！）
    min_cost = [10**18] * n
    q = []  # (qの中身)＝(dist, to)
    for v, cos in repn[0]: heappush(q, (cos, v))
    while q:
        dist, v = heappop(q)
        if min_cost[v] < dist: continue
        min_cost[v] = dist
        for nv, ncos in repn[v]:
            heappush(q, (dist + ncos, nv))
    #for v in range(n): print("min_cost[{}]={}".format(v, min_cost[v]))

    # 最小コストを探索
    ans = 10**18
    for v in range(1, n):
        d, i, j = id_to_string[v]
        if d == 0:
            substring = string[i][:j]
        else:
            substring = string[i][-j:]
        circular = True
        for i in range(len(substring)):
            if substring[i] != substring[-i-1]:
                circular = False
                break
        if circular: ans = min(ans, min_cost[v])
    if ans == 10**18:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()