Submission #16280049

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)
#define chmin(x,y) do { x = min((ll)x, (ll)y); }while(0)
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;

const ll INF = 1e18;
ll N;
map<string, ll> m;
vector<ll> c;
vector<string> s;

vector<pair<ll,string>> nxt(string remain) {
  ll cost = m[remain];
  vector<pair<ll,string>> res;
  if (remain.size() == 0) {
    return res;
  }

  //cout << "base: " << cost << " " << remain << endl;

  rep(i, N) {
    string L, R;
    if (remain[0] == '^') {
      L = remain.substr(1);
      R = s[i];
    } else {
      L = s[i];
      R = remain.substr(0, remain.size() - 1);
    }
    ll l = min(L.size(), R.size());
    bool ok = true;
    rep(j, l) {
      if (L[j] != R[R.size() - 1 - j]) ok = false;
    }
    if (!ok) continue;
    if (L.size() > R.size()) res.emplace_back(cost + c[i], "^" + L.substr(l));
    else                     res.emplace_back(cost + c[i], R.substr(0, R.size()-l) + "$");
  }

  for (auto &e : res) {
    if (e.second == "^" || e.second == "$") e.second = "";
    //cout << "nxt: " << e.first << " " << e.second << endl;
  }
  return res;
}

int main(void) {
  cin >> N;
  c.resize(N);
  s.resize(N);
  rep(i, N)
    cin >> s[i] >> c[i];

  priority_queue<pair<ll,string>, vector<pair<ll,string>>, greater<pair<ll,string>>> q;
  rep(i, N) {
    q.emplace(c[i], "^" + s[i]);
  }
  while (!q.empty()) {
    ll cost = q.top().first;
    string remain = q.top().second;
    q.pop();
    if (m.find(remain) == m.end()) m[remain] = INF;
    if (m[remain] <= cost) continue;
    m[remain] = cost;
    for (auto e : nxt(remain)) {
      q.emplace(e.first, e.second);
    }
  }

  ll ans = INF;
  for (auto e : m) {
    string str = e.first;
    if (str.size() > 0 && str[0] == '^') str = str.substr(1);
    if (str.size() > 0 && str[str.size()-1] == '$') str = str.substr(0, str.size()-1);
    bool ok = true;
    rep(i, str.size()) {
      if (str[i] != str[str.size()-1-i]) ok = false;
    }
    if (!ok) continue;
    chmin(ans, e.second);
  }
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:2:36: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i, x) for (ll i = 0; i < (x); i++)
      |                                    ^
./Main.cpp:78:5: note: in expansion of macro ‘rep’
   78 |     rep(i, str.size()) {
      |     ^~~

Judge Result