邮差送信 (15分)
C时间限制：1 毫秒 | C内存限制：3000 Kb
题目内容：
有一个邮递员要在n个城市之间来回送信。但有的城市之间有大路相连而有的没有路。
现在要由一个城市到另一个城市送信，中途最少要经过多少个其它的城市呢？
输入描述
第一行是n,k(1<=n<=10000, 1<=k<=20000)，接下来就是k行。这k行每行有两个数a,b(1<=a,b<= n)，表示城市a和b之间有大路k行以后就是两个数p和q。
输出描述
输出从城市p到城市q之间最少要经过的其它的城市的数目。如果p和q之间不连通则输出0
输入样例
6 6
1 4
1 2
2 3
3 4
5 4
5 6
1 6
输出样例
2
#include <iostream>
using namespace std;
int a[100][100]; //存路径
int far[100]; //求路径,即存储它的前一个结点
int n, m, p, q; //n个城市, m条路， p起点， q终点
int z[1000]; //模拟队列
int visit[100]; //标记是否访问过
void print(int w){
int count = 0;
// cout << "w" << w << endl;
while(far[w] != p){
count++;
w = far[w];
}
cout << count;
}
void dfs(){
int head = 1, tail = 2;
z[head] = p;
visit[p] = 1;
int flag = 1;
while(head < tail && flag){
for(int i = 1; i <= n; i++){
if(a[z[head]][i] == 1 && visit[i] == 0){
visit[i] = 1;
z[tail] = i;
tail++;
far[i] = z[head];
if(i == q){ //找到退出
// cout << "find" << endl;
flag = 0;
print(i);
break;
}
}
}
head++;
}
if(head == tail) //未找到
cout << 0;
}
int main(){
cin >> n >> m;
int x, y;
for(int i = 1; i <= m; i++){
cin >> x >> y;
a[x][y] = a[y][x] = 1;
}
cin >> p >> q;
dfs();
return 0;
}
原文：http://www.cnblogs.com/zhumengdexiaobai/p/7748027.html