Read problem statements in [Russian], [Mandarin Chinese], [Bengali], and [Vietnamese] as well.

You are given a string S consisting of N digits from 0 to 9. You want to obtain a palindrome from S using some operations. 

There are M different types of operations you can make on S. Each operation is described by three integers  X, Y and W. In this operation, if there is a digit equal to X in S, you can replace X with Y using W coins. For example, if X = 4, Y= 5, W = 10 and S = 1448, you make S equal to either 1458 or 1548 using 10 coins. 

You can do the operations in any order. One type of operation can be done multiple times. You can use at most K coins total in all operations. Among all the palindromes that can be obtained from S, output the lexicographically maximum palindrome.

If two strings A and B have the same length, we say that A is lexicographically larger than B if there exists an index i so that A_{1}=B_{1},A_{2}=B_{2},\ldots,A_{i-1}=B_{i-1}, A_{i}>B_{i}.

Print -1 if it is impossible to obtain a palindrome from S using at most K coins.

------ Input Format ------ 

- The first line contains an integer T, the number of test cases. Then the test cases follow.
- The first line of each test case contains three integers N, M, and K - the length of the string, the number of operation types, and the maximum number of coins to spend, respectively.
- The second line contains a string S of length N.
- Each of the next M lines contains three integers X_{i}, Y_{i} and W_{i} - the parameters of the i-th type of operation.

------ Output Format ------ 

For each test case, output the lexicographically maximum palindrome which can be obtained from the given string S using at most K coins. Print -1 if it is impossible to obtain a palindrome. 

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 90$
$0 ≤ K, W_{i} ≤ 10^{9}$
$0 ≤ X_{i}, Y_{i} ≤ 9$, $X_{i}\ne Y_{i}$
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3 
5 10 10
75643
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 0 1
4 5 1000000
1895
2 3 10
3 1 9
1 2 5
5 6 99
8 9 45
6 4 12
141746
1 5 3
5 7 2
7 9 10
6 1 5
----- Sample Output 1 ------ 
95759
-1
147741
----- explanation 1 ------ 
- In the first test case, we convert $7$ and $3$ into $9$ using two and six operations, respectively, $4$ into $5$ using one operation, and $6$ to $7$ using one operation. There is no way to obtain a palindrome which is lexicographically larger than $95759$ using ten operations.
- In the second test case, there is no possible way to convert $1$ and $5$ into equal digits. So we can't obtain a palindrome.
- In the third test case, we convert the $6$ in the last index of the given string into $1$ using the $4$-th type of operation. So $S$ becomes $141741$. Next, we convert $1$ in the third index into $5$ using the $1$-st type of operation. So $S$ becomes $145741$. Then we convert the $5$ in the third index of $S$ into $7$ using the $2$-nd type of operation. So $S$ becomes $147741$. The total cost is $5 + 3 + 2 = 10$ coins and the string we obtain after all operations is a palindrome. We can't obtain a lexicographically larger string than $147741$ using at most $12$ coins.

Difficulty: VERY_HARD
Tags: String algorithms

Shortest paths

Starter code:

Solutions:
def F():
	MAX = 10 ** 9 + 1
	for _ in range(int(input())):
		(N, M, K) = [int(x) for x in input().split()]
		S = [int(x) for x in input()]
		XYW = [[int(x) for x in input().split()] for i in range(M)]
		cost = [[MAX for i in range(10)] for j in range(10)]
		for i in range(10):
			cost[i][i] = 0
		for [x, y, w] in XYW:
			cost[x][y] = w
		for p in range(10):
			for i in range(10):
				for j in range(10):
					cost[i][j] = min(cost[i][j], cost[i][p] + cost[p][j])
		coins_used = [0] * (1 + N // 2)
		for p in range(N // 2, 0, -1):
			coins = MAX
			for i in range(10):
				coins = min(coins, cost[S[p - 1]][i] + cost[S[N - p]][i])
			coins_used[p - 1] = coins_used[p] + coins
		if coins_used[0] > K:
			print(-1)
			continue
		ans = ''
		extra_coins = K - coins_used[0]
		for p in range(N // 2):
			for i in range(9, -1, -1):
				this_cost = cost[S[p]][i] + cost[S[N - p - 1]][i]
				old_cost = coins_used[p] - coins_used[p + 1]
				if this_cost <= extra_coins + old_cost:
					ans += str(i)
					extra_coins -= this_cost - old_cost
					break
		if N % 2:
			for i in range(9, -1, -1):
				if extra_coins >= cost[S[N // 2]][i]:
					ans += str(i)
					break
		for i in range(N // 2 - 1, -1, -1):
			ans += ans[i]
		print(ans)
F()


import sys
import math

def read(lst=False):
	line = sys.stdin.readline().rstrip()
	if ' ' in line or lst:
		return map(int, line.split())
	return line

def floydWarshall(n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

def computeCost(n):
	totalCost = 0
	for i in range(N // 2):
		minCost = 1e+21
		for j in range(10):
			cost[i][j] = dp[int(S[i])][j] + dp[int(S[n - 1 - i])][j]
			if cost[i][j] < minCost:
				palin[i] = j
				minCost = cost[i][j]
		totalCost += minCost
	if n & 1:
		minCost = 1e+21
		for i in range(10):
			cost[-1][i] = dp[int(S[n // 2])][i]
			if cost[-1][i] < minCost:
				palin[-1] = i
				minCost = cost[-1][i]
		totalCost += minCost
	return totalCost

def solver(totalCost):
	for i in range((N + 1) // 2):
		for j in range(9, -1, -1):
			if totalCost - cost[i][palin[i]] + cost[i][j] <= K:
				totalCost += -cost[i][palin[i]] + cost[i][j]
				palin[i] = j
				break
T = int(read())
for t in range(T):
	(N, M, K) = read()
	S = read()
	dp = [[math.inf if i != j else 0 for i in range(10)] for j in range(10)]
	cost = [[None] * 10 for _ in range((N + 1) // 2)]
	palin = [None] * ((N + 1) // 2)
	for m in range(M):
		(X, Y, W) = read()
		if X != Y:
			dp[X][Y] = W
	floydWarshall(10)
	minCost = computeCost(N)
	if minCost > K:
		print(-1)
		continue
	solver(minCost)
	print(''.join(map(str, palin[:N // 2] + palin[N // 2::-1])))
sys.exit()


def move(op, root, node, price=0, looked=[]):
	if node != root:
		op[root][node] = min(op[root].get(node, float('inf')), price)
	for conn in list(op[node]):
		if not conn in looked:
			if conn in op[root] and op[root][conn] < price:
				continue
			move(op, root, conn, price + op[node][conn], looked + [conn])
for _ in range(int(input())):
	(n, M, K) = map(int, input().split())
	S = list(input())
	_S = S.copy()
	op = {str(i): {} for i in range(10)}
	for i in range(M):
		(x, y, w) = input().split()
		op[x][y] = int(w)
	for i in range(10):
		move(op, str(i), str(i))
	for i in range(10):
		op[str(i)][str(i)] = 0
	minC = 0
	changes = {}
	for i in range(n // 2):
		j = n - 1 - i
		if S[i] != S[j]:
			(a, b) = (S[i], S[j])
			(bo, bc) = (None, float('inf'))
			for g in range(10):
				g = str(g)
				if g in op[a] and g in op[b]:
					c = op[a][g] + op[b][g]
					if c < bc:
						bo = g
						bc = c
			if bo == None:
				print(-1)
				break
			else:
				minC += bc
				if bo == 'a':
					S[i] = S[j]
				else:
					S[j] = S[i]
				changes[i] = bc
	else:
		if minC > K:
			print(-1)
		else:
			for i in range(n // 2):
				j = n - 1 - i
				(a, b) = (_S[i], _S[j])
				discount = changes.get(i, 0)
				for g in range(9, -1, -1):
					g = str(g)
					if g in op[a] and g in op[b]:
						c = op[a][g] + op[b][g] - discount
						if c + minC <= K:
							S[i] = g
							S[j] = g
							minC += c
							break
			if n & 1:
				i = n // 2
				a = S[i]
				for g in range(9, -1, -1):
					g = str(g)
					if g in op[a]:
						c = op[a][g]
						if c + minC <= K:
							S[i] = g
							minC += c
							break
			print(''.join(S))


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	s = list(input().strip())
	s = list(map(int, s))
	d = [[float('inf') for i in range(10)] for i in range(10)]
	for i in range(m):
		(x, y, w) = map(int, input().split())
		d[x][y] = w
	for i in range(10):
		d[i][i] = 0
	for l in range(10):
		for i in range(10):
			for j in range(10):
				d[i][j] = min(d[i][j], d[i][l] + d[l][j])
	suff = [float('inf') for i in range(n // 2)]
	for i in range(n // 2):
		for j in range(10):
			x = d[s[i]][j]
			y = d[s[n - i - 1]][j]
			suff[i] = min(suff[i], x + y)
	suff.append(0)
	for i in range(n // 2 - 1, -1, -1):
		suff[i] += suff[i + 1]
	if suff[0] > k:
		print(-1)
		continue
	ans = [0 for i in range(n)]
	for i in range(n // 2):
		for j in range(9, -1, -1):
			x = d[s[i]][j]
			y = d[s[n - i - 1]][j]
			if suff[i + 1] + x + y <= k:
				ans[i] = j
				ans[n - i - 1] = j
				k -= x + y
				break
	if n & 1:
		for j in range(9, -1, -1):
			x = d[s[n // 2]][j]
			if x <= k:
				ans[n // 2] = j
				k -= x
				break
	print(''.join([str(i) for i in ans]))