学步园

这道题一直是TLE，超时，开始以为是算法的问题，后来才知道是输入的问题，太坑了

这道题可以用BFS来解， floyd也没有问题

但是一定要注意，输入单词对的时候，结束符分两种情况，一种是 几组连续输入中间的是空行为结束，最后一组数据是以EOF结束

注：注释掉的 有一部分是floyd算，但是一下正常的是用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;
        }
    }
}