2013年8月3日

UVa 117 - The Postal Worker Rings Once

#include <cstdio>
#include <cstring>

const int MAX = 26;
int dis[MAX][MAX], ans;

void run(int now) {
  for (int i = 0; i < MAX; i++) {
    if (dis[now][i]) {
      ans += dis[now][i];
      dis[now][i] = dis[i][now] = 0;
      run(i);
    }
  }
}

int main() {
  char s[9999];
  while (gets(s)) {
    memset(dis, 0, sizeof(dis));
    int rec[26] = {};
    while (strcmp(s, "deadend")) {
      int len = strlen(s);
      int a = s[0] - 'a', b = s[len - 1] - 'a';
      dis[a][b] = dis[b][a] = len;
      rec[a]++;
      rec[b]++;
      gets(s);
    }
    ans = 0;
    int v1 = -1, v2 = -1;
    for (int i = 0; i < MAX; i++) {
      if (rec[i] & 1) {
        if (v1 == -1) {
          v1 = i;
        } else {
          v2 = i;
        }
      }
    }
    if (v1 != -1) {
      int d[MAX];
      bool vis[MAX] = {};
      for (int i = 0; i < MAX; i++) {
        d[i] = 2e9;
      }
      d[v1] = 0;
      while (1) {
        int a = -1, min = 2e9;
        for (int i = 0; i < MAX; i++) {
          if (!vis[i] && d[i] < min) {
            a = i;
            min = d[i];
          }
        }
        if (a == -1) {
          break;
        }
        vis[a] = true;
        for (int b = 0; b < MAX; b++) {
          if (dis[a][b] && d[b] > d[a] + dis[a][b]) {
            d[b] = d[a] + dis[a][b];
          }
        }
      }
      ans += d[v2];
    }
    for (int i = 0; i < MAX; i++) {
      if (rec[i]) {
        run(i);
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言