最少转车次数

题目描述:

小华从某起点到某目的地需要经过若干次公交转车( 乘车不存在绕圈现象，但不保证可以到达目的地 ），显然坐车的方案可能不唯一。如下图所示，从起点A到目的地H可以选择公交线路“A -> D -> E -> F -> H”，也可以选择公交线路“A -> D -> G -> H”。前者需要在“D”、“E”、 “F”三个公交车站下车后转车3次，而后者只需要在“D”和“G”两个公交车站下车后转车2次，且是所有乘坐公交车方案里转车次数最少的一种方案。

现给出某公交车坐车方案图，求从起点A到目的地的最少转车方案。

输入格式:

第一行三个整数 n, m，n表示图中的顶点数，m表示有向图的边数；

接下来共m行,每行两个整数(i,j)，为图G中的一条有向边；

最后一行一个字母，表示目的地。

输出格式:

一个数，表示最少的转车次数。

数据范围:

图中顶点数小于26个，边数小于50条。

样例输入:

8 10
A B
A D
B C
C F
D E
E C
E F
D G
F H
G H
H

样例输出:

2

提示:

请完善以下程序：

#include <bits/stdc++.h>
using namespace std;
int a[27][27],b[27], n, m, to, c;
int q[27], head, tail;
bool f[27], flag;
char x, y ;

int main() {
	cin >> n >> m;
	for ( int i=1; i<=m; i++) {       //读入m条边，建图
		cin >> x >> y;  //读入两个能够直达的车站编号
		________(1)__________ 
	}
	head =0;
	tail = 0;
	q[tail] = 0 ;        //把起始节点 A放入队列，A的编号为0
	______(2)_______
	f[0] = true;
	b[0] = 0;
	cin >> x;  //读入目标车站编号
	to = x - 'A';
	flag = false;
	while ( head<tail && flag == false ) {   //广搜：队列不为空，并且没有找到目标车站
		_________(3)_________
		head += 1;
		for ( int j=0; j<n; j++) {    //队头的元素，和其他所有的顶点看看有没有边，有则把它拉进队列
			if ( j != to &&  a[c][j] == 1 && f[j] == false) {
				q[ tail ] = j;
				tail += 1;
				f[j] = true;
				b[j] = b[c] +1;
			} else if (  j == to && a[c][j] == 1) {
				________(4)________    //转车次数，等于长度减1
				________(5)________
				break;
			}
		}
	}
	if ( flag == false) printf( "NO PATH!" );
	return 0;
}

时间限制: 1000ms
空间限制: 256MB

---

来源: 高中教材