Language: C++

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int MOD = 1e9 + 7;
const LL INF = 1e18 + 9;
const int MX = 1e5 + 5;

int n;
vector<string> inp;
vector<LL> cost;

bool isPalindrome(string &s) {
	int l = s.size();
	for(int i=0;i<l;i++) {
		if(s[i] != s[l-1-i])
			return false;
	}
	return true;
}

vector<string> getNextState(string &s1, string &s2) {
	vector<string> ret;

	int l1 = s1.size();
	int l2 = s2.size();
	int l = min(l1,l2);
	for(int i=0;i<l;i++) {
		if(s1[i] != s2[l2-1-i]) {
			return ret;
		}
	}
	if(l1 == l2) {
		ret.push_back("");
		ret.push_back("");
	}	
	else if(l1 > l2) {
		string tmp = s1.substr(l2);
		ret.push_back(tmp);
		ret.push_back("");
	}
	 else {
		string tmp = s2.substr(0, l2-l1);
		ret.push_back("");
		ret.push_back(tmp);
	}
	return ret;
} 

map<pair<string, string>, LL > cache;

LL solve(string &pre, string &suff) {
	if(isPalindrome(pre + suff)) {
		return 0;
	}

	if(cache.find({pre,suff}) != cache.end()) {
		return cache[{pre,suff}];
	}

	LL ret = INF;

	for(int i=0;i<n;i++) {
		vector<string> cand;
		if(pre.size() > 0) {
			cand = getNextState(pre, inp[i]);
		} else {
			cand = getNextState(inp[i], suff);
		}

		if(cand.size() == 0) {
			continue;
		}

		ret = min(ret, cost[i] + solve(cand[0], cand[1]));
	}

	cache[{pre, suff}] = ret;
	return ret;
}

int main() {
	cin >> n;
	inp.resize(n);
	cost.resize(n);
	for(int i=0;i<n;i++) {
		cin >> inp[i] >> cost[i];
	}

	LL ans = INF;
	for(int i=0;i<n;i++) {
		ans = min(ans, cost[i] + solve(inp[i], ""));
	}
	if(ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;

	return 0;
}


Compiler output:
a.cc: In function 'long long int solve(std::string&, std::string&)':
a.cc:54:29: error: cannot bind non-const lvalue reference of type 'std::string&' {aka 'std::__cxx11::basic_string<char>&'} to an rvalue of type 'std::__cxx11::basic_string<char>'
   54 |         if(isPalindrome(pre + suff)) {
      |                         ~~~~^~~~~~
a.cc:14:27: note:   initializing argument 1 of 'bool isPalindrome(std::string&)'
   14 | bool isPalindrome(string &s) {
      |                   ~~~~~~~~^
a.cc: In function 'int main()':
a.cc:93:56: error: cannot bind non-const lvalue reference of type 'std::string&' {aka 'std::__cxx11::basic_string<char>&'} to an rvalue of type 'std::string' {aka 'std::__cxx11::basic_string<char>'}
   93 |                 ans = min(ans, cost[i] + solve(inp[i], ""));
      |                                                        ^~
In file included from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/basic_string.h:646:7: note:   after user-defined conversion: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const _Alloc&) [with <template-parameter-2-1> = std::allocator<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]'
  646 |       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
      |       ^~~~~~~~~~~~
a.cc:53:31: note:   initializing argument 2 of 'long long int solve(std::string&, std::string&)'
   53 | LL solve(string &pre, string &suff) {
      |                       ~~~~~~~~^~~~