SRM 509 D1 500

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABCS 'z'-'a'+2
#define EMPTY ABCS-1
#define INF 1000000000

class PalindromizationDiv1 {
    vector<vector<int> > dist;

    int getCost(const string& s1, const string& s2)
    {
        int mN=s1.size();
        int mM=s2.size();
        //edit distance s1 vs s2
        vector<vector<int> > dp(mN+1,vector<int> (mM+1,INF));
        dp[0][0]=0;
        REP(i,mN+1)
        REP(j,mM+1)
        {
            if(i<mN && j<mM && dp[i][j]+dist[s1[i]-'a'][s2[j]-'a']<dp[i+1][j+1])
                dp[i+1][j+1]=dp[i][j]+dist[s1[i]-'a'][s2[j]-'a'];
            if(i<mN && dp[i][j]+dist[EMPTY][s1[i]-'a']<dp[i+1][j])
                dp[i+1][j]=dp[i][j]+dist[EMPTY][s1[i]-'a'];
            if(j<mM && dp[i][j]+dist[EMPTY][s2[j]-'a']<dp[i][j+1])
                dp[i][j+1]=dp[i][j]+dist[EMPTY][s2[j]-'a'];
        }
        return dp[mN][mM];
    }

public:
    int getMinimumCost( string word, vector <string> op )
    {
        dist.resize(ABCS,vector<int>(ABCS,INF));
        REP(i,op.size())
        {
            stringstream ss(op[i]);
            string mop;
            char c1=' ', c2=' ';
            int tmp=0;
            if(op[i][0]=='c')
            {
                ss >> mop >> c1 >> c2 >> tmp;
                dist[c1-'a'][c2-'a']=tmp;
            }
            else
            {
                ss >> mop >> c1 >> tmp ;
                if (mop[0]=='a')
                {
                    dist[EMPTY][c1-'a']=tmp;
                }
                else
                {
                    dist[c1-'a'][EMPTY]=tmp;
                }
            }
        }
        REP(i,ABCS)
            dist[i][i]=0;
        //Floyd Warshall
        REP(k,ABCS)
        REP(i,ABCS)
        REP(j,ABCS)
        {
            if(dist[i][j]>dist[i][k]+dist[k][j])
                dist[i][j]=dist[i][k]+dist[k][j];
        }
        //opt
        vector<vector<int> > dist2=dist;
        REP(k,ABCS)
        REP(i,ABCS)
        REP(j,ABCS)
        {
            if(dist2[i][j]>dist[i][k]+dist[j][k])
                dist2[i][j]=dist[i][k]+dist[j][k];
        }
        REP(i,ABCS)
        REP(j,ABCS)
        {
            if(dist2[i][j]<dist2[j][i])
                dist2[i][j]=dist2[j][i];
        }
        dist2.swap(dist);
        int n=word.size();
        int best=INF;
        REP(cut,n)
        {
            string s1=word.substr(0,cut),s2=word.substr(cut),s3=word.substr(cut+1);
            reverse(s2.begin(),s2.end());
            reverse(s3.begin(),s3.end());
            int tmp=getCost(s1,s2);
            if(tmp<best)
                best=tmp;
            tmp=getCost(s1,s3);
            if(tmp<best)
                best=tmp;
        }
        if(best>=INF)
            return -1;
        return best;
    }
};