Babel

The Problem

John and Mary are brothers, and are enthusiastic about their courses on foreign languages. Each of the brothers is taking several language courses. When they get home they comment on grammar, vocabulary, culture of the different countries and so on. In one of those conversations they realized some words are common to more than one language, even though the words may have different meanings in the languages. For example, the word "amigo" exists in Portuguese and Spanish and has the same meaning, while "date" is a word that exists in English and French and may have different meanings, since "date" is also a fruit, besides meaning a calendar date. On the other hand, "red" in Spanish is a network, while in English it is a color.

Thrilled by these findings, the brothers decided to write in a notepad all words in common they could think of, associating each word to a pair of languages. Observant and smart, John proposed a challenge to Mary: given one language to start and one language to finish, write down a sequence of words such that the first word is included in the vocabulary of the start language, and the last word is included in the vocabulary of the finish language. Two adjacent words in the sequence must be in the vocabulary of the same language. For example, if the start language is Portuguese and the finish language is French, Mary could write the sequence "amigo actual date" (Portuguese/Spanish, Spanish/English, English/French).

To John's surprise, Mary solved the problem rather easily. Annoyed by his sister's success, he decided to make the problem more difficult: Mary must find a solution in which the sequence has the smallest number of letters in total (not counting spaces between words), and, besides, two consecutive words must not have the same initial letter.

Note that the previous solution is now invalid, as "amigo" and "actual" share the same initial letter. It is possible, however, to find another solution, "amigo red date", with a total length equal to 12.

John did an extensive research on the Internet and compiled an enormous list of words, and challenged Mary to solve the problem. As there may be more than one solution, he asked her to answer if there is a solution, and in that case to answer the number of letters in the best solution. Can you help Mary?

The Input

The input contains several test cases. The first line of a test case contains one integer M (1 ≤ M ≤ 2000), representing the total number of words compiled by John. The second line contains two distinct strings O and D, separated by one space, indicating respectively the start language and the finish language. Each of the next M lines contains three strings I₁, I₂ and P, separated by one space, representing respectively two languages and one word in common between both languages (I₁ and I₂ are always distinct). All strings will have length at least 1 and at most 50, and will be composed of lower case letters only. The same pair of languages may have several words associated to it, but a word P will be never repeated in a test case.

The end of input is indicated by a line containing only one zero.

The Output

For each test case in the input, your program must print a line with a single integer, the length of the shortest sequence that satisfies John's restrictions, or the word "impossivel" (lowercase, meaning "impossible" in Portuguese) in case it is not possible.

Sample Input

4
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
4
portugues alemao
ingles espanhol red
espanhol portugues amigo
frances ingles date
espanhol ingles actual
6
portugues frances
ingles espanhol red
espanhol portugues amigo
frances ingles date
frances espanhol la
portugues ingles a
espanhol ingles actual
0

Sample Output

12
impossivel
5

---

題目描述：
天殺的, 看了好久才明白。
求一個最短的序列, 相鄰的單字有在同一種語言中被定義, 且相鄰兩個單字不可以擁有同一個首字母。
會給定起始要求的語言 以及 目標結束的語言, 以及一個單字在哪兩個語言中被定義。

題目解法：

轉換成最短路徑的思路即可, 但對於每個節點多了一個屬性, 
上次是接什麼字母, 要避免接下來接相同的字母。
下面是用 spfa 的方式去更新

#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct E {
    int to, fl, len;//to, first letter, length
};
vector<E> g[5005];
int main() {
    int n, i, j, k;
    char O[105], D[105], I1[105], I2[105], word[105];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < 5000; i++)
            g[i].clear();
        map<string, int> LANG;
        int lsize = 0;
        scanf("%s %s", &O, &D);
        LANG[O] = ++lsize, LANG[D] = ++lsize;
        while(n--) {
            scanf("%s %s %s", &I1, &I2, &word);
            int &x1 = LANG[I1];
            int &x2 = LANG[I2];
            if(x1 == 0) x1 = ++lsize;
            if(x2 == 0) x2 = ++lsize;
            E tmp;
            tmp.to = x2, tmp.fl = word[0]-'a', tmp.len = strlen(word);
            g[x1].push_back(tmp);
            tmp.to = x1;
            g[x2].push_back(tmp);
        }
        int dist[5005][26], inq[5005][26];
        memset(dist, 63, sizeof(dist));
        memset(inq, 0, sizeof(inq));
        queue<int> Qn, Ql;
        dist[1][0] = 0;
        Qn.push(1), Ql.push(0);
        while(!Qn.empty()) {
            int tn = Qn.front();
            int tl = Ql.front();
            Qn.pop(), Ql.pop();
            inq[tn][tl] = 0;
            for(vector<E>::iterator it = g[tn].begin();
                it != g[tn].end(); it++) {
                if(it->fl != tl || tn == 1) {
                    if(dist[it->to][it->fl] > dist[tn][tl] + it->len) {
                        dist[it->to][it->fl] = dist[tn][tl] + it->len;
                        if(inq[it->to][it->fl] == 0) {
                            Qn.push(it->to);
                            Ql.push(it->fl);
                            inq[it->to][it->fl] = 1;
                        }
                    }
                }
            }
        }
        int ret = 0xfffffff;
        for(i = 0; i < 26; i++)
            ret = min(ret, dist[2][i]);
        if(ret == 0xfffffff)
            puts("impossivel");
        else
            printf("%d\n", ret);
    }
    return 0;
}