#include #include #include #include #include #include using namespace std; typedef pair PII; const int INF = numeric_limits::max()/3; vector kbd = {"QWERTYUIOP","ASDFGHJKL","ZXCVBNM"}; vector positions('Z'-'A'+1); void preproc(){ for(unsigned i=0; i>s; vector> cost('Z'-'A'+1, vector('Z'-'A'+1,INF)); cost['F'-'A']['J'-'A']=0; for(unsigned t=0;t> costnext('Z'-'A'+1, vector('Z'-'A'+1,INF)); for(int i=0;i<'Z'-'A'+1; ++i){ for(int j=0;j<'Z'-'A'+1; ++j){ costnext[i][c] = min( costnext[i][c], cost[i][j]+dist(j,c) ); costnext[c][j] = min( costnext[c][j], cost[i][j]+dist(i,c) ); } } costnext.swap(cost); } int mn=INF; for(int i=0;i<'Z'-'A'+1; ++i){ for(int j=0;j<'Z'-'A'+1; ++j){ mn = min(mn,cost[i][j]); } } cout<