Uva 429 Word 변환 (최 단 경로)

이 문 제 는 줄곧 TLE 로 시간 을 초과 하여 처음에는 알고리즘 의 문제 인 줄 알 았 는데, 후에 야 입력 의 문제 라 는 것 을 알 게 되 었 다. 너무 애매 하 다.
이 문 제 는 BFS 로 풀 수 있 고 플 로 이 드 도 문제 가 없다.
그러나 단 어 를 입력 할 때 종료 부 호 는 두 가지 상황 으로 나 뉘 는데 하 나 는 몇 조 가 중간 에 연속 으로 입력 하 는 것 은 빈 행동 으로 끝 나 는 것 이 고 마지막 데 이 터 는 EOF 로 끝 나 는 것 입 니 다.
주: 주석 이 떨 어 진 부분 은 플 로 이 드 로 계산 하지만, 정상 적 인 것 은 BFS 로 문 제 를 푸 는 것 입 니 다.
코드:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;

const int N = 300;
const int INF = 1000000;
int T, id;
int g[N][N], d[N];
map <string, int> mp;
string s1, s2, s[N];
int bfs( int st, int en ) {
    queue< int > q;
    q.push(st);
    for ( int i = 0; i <= id; ++i ) d[i] = INF;
    d[st] = 0;
    while ( !q.empty() ) {
        int u = q.front(); q.pop();
        if ( u == en ) break;
        for ( int i = 0; i < id; ++i ) if ( g[u][i] && d[i] > d[u] + 1 ) {
            q.push(i);
            d[i] = d[u]+1;
        }
    }
    return d[en];
}
    
int main()
{
    bool f = false;
    scanf("%d", &T);
    getchar();
    while ( T-- ) {
        if ( f ) cout << endl;
        f = true, id = 0;
        //for ( int i = 0; i < N; ++i ) for ( int j = i; j < N; ++j ) g[i][j] = g[j][i] = INF;
        memset(g, 0, sizeof(g));
        mp.clear();
        while ( cin >> s[id] && s[id] != "*" ){
            if ( !mp[s[id]] ) {
                mp[s[id]] = id; 
                for ( int i = 0; i < id; ++i )  
                    if ( s[id].size() == s[i].size() ) {
                        int num = 0;
                        for ( int k = 0; k < s[id].size() && num < 2; ++k ) if ( s[id][k] != s[i][k] ) num++; 
                        if ( num == 1 ) g[id][i] = g[i][id] = 1;
                    }
                id++;
            }
        }
        //for ( int k = 0; k < id; ++k )  for ( int i = 0; i < id; ++i ) for ( int j = 0; j < id; ++j )  
          //  if ( g[i][k] + g[k][j] < g[i][j] ) g[i][j] = g[i][k] + g[k][j];
        char ch;
        getchar();
        while ( ( ch = getchar() ) != 0xa && ch != EOF ) {
            cin >> s1;
            s2.clear();
            s2 += ch; s2 += s1; cin >> s1;
            getchar();
            int u = mp[s2], v = mp[s1];
            cout << s2 << " " << s1 << " " << bfs( u, v ) << endl;
        }
    }
}