题目链接: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;
}
04-05 19:23