提出 #15936454

---

ソースコード 拡げる

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>

using namespace std;

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

long long ret;

map<pair<string, string>, long long> cache;
priority_queue<pair<long long, pair<string, string>>> heap;

void add_to_heap(const string& s1, const string& s2, long long cost) {
	auto s = make_pair(s1, s2);
	auto it = cache.find(s);
	if (it != cache.end() && cost >= it->second) {
		return;
	}
	cache[s] = cost;
	heap.push(make_pair(-cost, s));
}

void add(const string& s1, const string& s2, long long cost) {
	if (cost >= ret) {
		return;
	}
	int l1 = s1.length();
	int l2 = s2.length();
	int l = min(l1, l2);
	for (int i = 0; i < l; ++i) {
		if (s1[i] != s2[l2 - 1 - i]) {
			return;
		}
	}
	if (l1 == l2) {
		ret = min(ret, cost);
		return;
	}
	if (l1 > l2) {
		string s = s1.substr(l2);
		if (is_palindrome(s)) {
			ret = min(ret, cost);
			return;
		}
		add_to_heap(s, "", cost);
	}
	else {
		string s = s2.substr(0, l2 - l1);
		if (is_palindrome(s)) {
			ret = min(ret, cost);
			return;
		}
		add_to_heap("", s, cost);
	}
}

int main()
{
#ifdef _MSC_VER
	freopen("f.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> s(n);
	vector<long long> c(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i] >> c[i];
	}
	ret = (1LL << 62);
	for (int i = 0; i < n; ++i) {
		add(s[i], "", c[i]);
	}
	while (!heap.empty()) {
		auto w = heap.top().second;
		long long cost = -heap.top().first;
		heap.pop();
		if (cost != cache[w]) {
			continue;
		}
		for (int i = 0; i < n; i++) {
			if (w.first == "") {
				add(w.first + s[i], w.second, cost + c[i]);
			} else {
				add(w.first, s[i] + w.second, cost + c[i]);
			}
		}
	}
	if (ret >= (1LL << 62)) {
		ret = -1;
	}
	cout << ret << endl;
	return 0;
}

提出情報

ジャッジ結果