题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1837
描述：
Isenbaev是国外的一个大牛。
现在有许多人要参加ACM ICPC。
一共有n个组，每组3个人。同组的3个人都是队友。
大家都想知道自己与大牛的最小距离是多少。
大牛与自己的最小距离当然是0。大牛的队友和大牛的最小距离是1。大牛的队友的队友和大牛的最小距离是2……以此类推。
如果实在和大牛没有关系的只好输出undefined了。
第一行读入n。表示有n个组。1 ≤ n ≤ 100
接下来n行，每行有3个名字，名字之间用空格隔开。每个名字的开头都是大写的。
每行输出一个名字，名字后面空格后输出数字a或者字符串undefined，a代表最小距离。
名字按字典序输出。
思路：
这一题我做的相当纠结，整了好几个小时。其实思路很简单，就是从Isenbaev这个人开始bfs，由于bfs可以记录每个点到起始搜索点的最短距离，正好就是答案。但是要注意没有Ixenbaev的情况，我已开始就栽在这了。
但是有几个问题：1:建图问题。每个点不是 int了，都是string类型，不好建图。后来想了想就用 了stl的map，把每个人名和int型映射，int就代表这个节点。先把所有人名插入到map里面，（这时已经按照字典序排列了，map容器的特性）。这样就建好图了。每个人名都有个int编号了，就用邻接矩阵建图再bfs就好了。bfs记录每个节点的dis[] 是多少，可以看看算法导论上这一节讲的挺好的。
2特殊case。有些情况是这组人没有一个人是 Isenbaev，这时候所有人都是undefined.一开始就没考虑到结果runtime error #3.
//g++ 4.7.2 0.031s
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <string> //Don't forget this,or failed compile by vc++
using namespace std;
const int M = 300;
bool adj[M][M], vis[M]; //adj[][]邻接矩阵
int n, dis[M];
void bfs(int start)
{
int u;
queue<int> q;
u = start;
dis[u] = 0;
q.push(u);
vis[u] = 1;
while (!q.empty())
{
u = q.front(); q.pop();
for (int v = 1; v <= n; ++v)
{
if (!vis[v] && adj[u][v])
{
vis[v] = 1;
dis[v] = dis[u] + 1; //记录距离
q.push(v);
}
}
}
}
int main()
{
int casenum;
scanf("%d", &casenum);
string name[M][4];
std::map<string, int> t;
for (int i = 1; i <= casenum; ++i)
for (int j = 1; j <= 3; ++j)
{
cin >> name[i][j]; //先把输入存在name[][]里面
t.insert(make_pair(name[i][j], 0));
}
int num = 1;
std::map<string, int>::iterator it;
for (it = t.begin(); it != t.end(); ++it) //给按照字典序排好的人名映射编号作为图的结点
(*it).second = num++;
for (int i = 1; i <= casenum; ++i)
{
int it1 = (*t.find(name[i][1])).second, it2 = (*t.find(name[i][2])).second, //找到这三个点，建立邻接矩阵
it3 = (*t.find(name[i][3])).second;
adj[it1][it2] = adj[it2][it3] = adj[it1][it3] = 1;
adj[it2][it1] = adj[it3][it2] = adj[it3][it1] = 1; //无向图，一开始忘了这一句害我调试半天
}
n = t.size(); //有多少个不同的人
it = t.find("Isenbaev");
if (it == t.end()) //处理没有Isenbaev的特殊情况
{
for (it = t.begin(); it != t.end(); ++it)
cout << (*it).first << " " << "undefined" << endl;
return 0;
}
bfs((*it).second);
for (it = t.begin(); it != t.end(); ++it)
{
if (dis[(*it).second] == 0 && (*it).first != "Isenbaev") //处理不连通的点，此时它的dis是0，但不是Isenbaev
cout << (*it).first << " " << "undefined" << endl;
else
cout << (*it).first << " " << dis[(*it).second] << endl;
}
return 0;
}