UVa1235

UVa1235
MSTを求めるだけ。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

int roll(string a, string b)
{
  int sum = 0;
  for (int k = 0; k < (int)4; ++k) {
    char mx = max(a[k], b[k]);
    char mn = min(a[k], b[k]);
    sum += min(mx - mn, (10 + mn - mx) % 10);
  }
  return sum;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;    
    string num[n];
    for (int i = 0; i < (int)n; ++i) {
      cin >> num[i];      
    }

    const int inf = 1 << 30;
    int g[n][n];
    fill(&g[0][0], &g[n - 1][n], inf);
    for (int i = 0; i < (int)n; ++i) {
      for (int j = 0; j < (int)n; ++j) {
        if (i != j) g[i][j] = roll(num[i], num[j]);
      }
    }

    bool vis[n];
    fill(vis, vis + n, false);

    int cost[n];
    fill(cost, cost + n, inf);
    cost[0] = 0;

    while (true) {
      int mn = inf;
      int idx;
      for (int i = 0; i < (int)n; ++i) {
        if (vis[i]) continue;
        if (mn > cost[i]) {
          mn = cost[i];
          idx = i;
        }
      }
      if (mn == inf) break;
      vis[idx] = true;
      for (int i = 0; i < (int)n; ++i) {                
        if (!vis[i]) cost[i] = min(cost[i], g[idx][i]);
      }
    }
    int mn = inf;
    for (int i = 0; i < (int)n; ++i) {
      mn = min(mn, roll("0000", num[i]));
    }
    cout << accumulate(cost, cost + n, mn) << endl;
  }

  return 0;
}