uva 10009 - All Roads Lead Where?

  1 /*
  2  Problem link
  3  Type: Graph
  4  Algorithm: BFS
  5  */
  6  #include <iostream>
  7  #include <cstdlib>
  8  #include <cstring>
  9  #include <cstdio>
 10  #include <map>
 11  #include <cmath>
 12  #include <vector>
 13  #include <queue>
 14  using namespace std;
 15  
 16  const int maxn = 100;
 17  
 18  bool a[maxn][maxn];
 19  map<char,int> City;
 20  map<int,char> CityName;
 21  int n,q;
 22  
 23  void readfile();
 24  string FindPath(char c1,char c2);
 25  
 26  int main()
 27  {
 28      int ntest;
 29      cin >> ntest;
 30      for (int test=1; test<=ntest; test++)
 31      {
 32          if (test>1) cout << endl;
 33          City.clear();
 34          CityName.clear();
 35          memset(a,false,sizeof(a));
 36          readfile();
 37          for (int i=1; i<=q; i++)
 38          {
 39              string c1,c2;
 40              cin >> c1 >> c2;
 41              cout << FindPath(c1[0],c2[0]) << endl;
 42          }
 43      }
 44      return 0;
 45  }
 46  
 47  void readfile()
 48  {
 49      n = 0;
 50      int m;
 51      cin >> m >> q;
 52      for (int i=1; i<=m; i++)
 53      {
 54          string c1,c2;
 55          cin >> c1 >> c2;
 56          map<char,int>::iterator iter = City.find(c1[0]);
 57          if (iter == City.end())
 58          {
 59              City[c1[0]] = ++n;
 60              CityName[n] = c1[0];
 61          }
 62          iter = City.find(c2[0]);
 63          if (iter == City.end())
 64          {
 65              City[c2[0]] = ++n;
 66              CityName[n] = c2[0];
 67          }
 68          a[City[c1[0]]][City[c2[0]]] = true;
 69          a[City[c2[0]]][City[c1[0]]] = true;
 70      }
 71  }
 72  
 73  string FindPath(char c1,char c2)
 74  {
 75      int x = City[c1];
 76      int y = City[c2];
 77      queue<int> q;
 78      bool visited[maxn];
 79      int pre[maxn];
 80      memset(visited,false,sizeof(visited));
 81      q.push(x);
 82      pre[x] = 0;
 83      do
 84      {
 85          int xx = q.front();
 86          q.pop();
 87          visited[xx] = true;
 88          for (int i=1; i<=n; i++)
 89              if (a[xx][i] && !visited[i])
 90              {
 91                  pre[i] = xx;
 92                  if (i==y)
 93                  {
 94                      string result = "";
 95                      while (pre[y]!=0)
 96                      {
 97                          result = CityName[y]+result;
 98                          y = pre[y];
 99                      }
100                      result = CityName[x]+result;
101                      return(result);
102                  }
103                  q.push(i);
104              }
105      } while (true || !q.empty());
106  }