範例程式碼 uva10150

//uva10150
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
vector<vector<int>> g;
vector<int> parent;
void BFS(int beg, int end){
    parent.assign(g.size(), -1);
    queue<int> q;
    q.push(beg);
    parent[beg] = beg;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0; i<g[cur].size(); i++){
            if(parent[g[cur][i]]==-1){
                parent[g[cur][i]] = cur;
                if(g[cur][i]==end)
                    return;
                q.push(g[cur][i]);
            }
        }
    }
}
int main(){
    string s;
    vector<string> v;
    while(getline(cin, s)){
        if(s=="")break;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    g.assign(v.size(), vector<int>());
    for(int i=0; i<v.size(); i++){
        string alpha="abcdefghijklmnopqrstuvwxyz";
        for(int j=0;j<min(int(v[i].size()), 16);++j){
            for(char c:alpha){
                string tmp=v[i];
                if(tmp[j]==c) continue;
                tmp[j]=c;
                auto it = lower_bound(v.begin(), v.end(), tmp);
                if(it!=v.end() && *it==tmp){
                    g[i].push_back(it-v.begin());
                    g[it-v.begin()].push_back(i);
                }
            }
        }
    }
    for(auto& vec:g)
        sort(vec.begin(), vec.end());
    int kase=0;
    string beg, end;
    while(cin>>beg>>end){
        if(kase++)cout<<endl;
        int b=find(v.begin(), v.end(), beg)-v.begin(), e=find(v.begin(), v.end(), end)-v.begin();
        BFS(b, e);
        vector<int> path;
        path.push_back(e);
        for(int cur=e; cur>=0 && cur!=parent[cur]; cur=parent[cur]){
            if(cur>=0)path.push_back(parent[cur]);
        }
        reverse(path.begin(), path.end());
        if(path.size() && path[0]==b){
            for(int &e: path){
                cout<<v[e]<<endl;
            }
        }
        else
            cout<<"No solution."<<endl;
    }
}