AOJ1320.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int Weight;
const Weight INF = 1000000000;
struct Edge{ int src, dest; Weight weight; };

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Weight shortestHamiltonPath(Matrix w, vector<int> s) {
  int n = w.size(), N = 1 << n;
  vector<vector<int>> best(N, vector<int>(n));
  REP(v,N) REP(i,n) best[v][i] = INF;
  REP(i,s.size()) best[1<<i][i] = s[i];
  REP(v,N) REP(i,n) if (v & (1 << i))
    REP(j,n) if (best[v|(1<<j)][j] > best[v][i] + w[i][j])
      best[v|(1<<j)][j] = best[v][i] + w[i][j];
  auto it = best[N-1].begin();
  int t = min_element(it, it + n) - it;
  return best[N-1][t];
}

int main() {
  int n;
  while (cin >> n, n) {
    vector<string> str(n), vs;
    vector<bool> fs(n, true);
    REP(i,n) cin >> str[i];
    REP(i,n) REP(j,n) if (i != j && str[i].find(str[j], 0) != string::npos) fs[j] = false;
    REP(i,n) if (fs[i]) vs.push_back(str[i]);
    n = vs.size();
    
    Matrix mat(n, vector<Weight> (n, INF));
    vector<Weight> s(n);
    REP(i,n) s[i] = vs[i].size();
    REP(i,n) REP(j,n) REP(k,min(vs[i].size(),vs[j].size())) {
      if (vs[i].substr(vs[i].size() - k) == vs[j].substr(0, k))
        mat[i][j] = min(mat[i][j], (int)vs[j].size() - k);
    }
    Weight res = shortestHamiltonPath(mat, s);
    cout << res << endl;
  }
  return 0;
}