2013年9月2日

UVa 11492 - Babel

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define PB push_back
using namespace std;

struct Node {
  Node(int index, int len, int head) : index(index), len(len), head(head) {}
  bool operator<(const Node & other) const {
    return (len > other.len);
  }
  int index, len, head;
};

const int SIZE = 4000;

int main() {
  int M;
  while (scanf("%d", &M) && M) {
    vector<int> con[SIZE], d[SIZE], letter[SIZE];
    char start[99], end[99];
    scanf("%s%s", start, end);
    map<string, int> indexOf;
    int N = 0;
    while (M--) {
      char s1[99], s2[99], word[99];
      scanf("%s%s%s", s1, s2, word);
      int a, b;
      if (indexOf.find(s1) != indexOf.end()) {
        a = indexOf[s1];
      } else {
        a = N;
        indexOf[s1] = N++;
      }
      if (indexOf.find(s2) != indexOf.end()) {
        b = indexOf[s2];
      } else {
        b = N;
        indexOf[s2] = N++;
      }
      con[a].PB(b);
      con[b].PB(a);
      int len = string(word).length();
      d[a].PB(len);
      d[b].PB(len);
      letter[a].PB(word[0] - 'a');
      letter[b].PB(word[0] - 'a');
    }
    if (string(start) == string(end)) {
      puts("0");
    } else if (indexOf.find(start) != indexOf.end() && indexOf.find(end) != indexOf.end()) {
      priority_queue<Node> pq;
      pq.push(Node(indexOf[start], 0, -1));
      int dis[SIZE][26];
      for (int i = 0; i < N; i++) {
        fill(dis[i], dis[i] + 26, 1e8);
      }
      while (!pq.empty()) {
        Node now = pq.top();
        pq.pop();
        int a = now.index;
        for (int i = 0; i < con[a].size(); i++) {
          int b = con[a][i];
          int head = letter[a][i];
          if (now.head != head && now.len + d[a][i] < dis[b][head]) {
            dis[b][head] = now.len + d[a][i];
            pq.push(Node(b, dis[b][head], head));
          }
        }
      }
      int ans = 1e8;
      for (int i = 0; i < 26; i++) {
        ans = min(ans, dis[indexOf[end]][i]);
      }
      if (ans >= 1e8) {
        puts("impossivel");
      } else {
        printf("%d\n", ans);
      }
    } else {
      puts("impossivel");
    }
  }
  return 0;
}

沒有留言:

張貼留言