最少转车次数
提交数: 96, 通过率: 53.13%, 平均分: 62.76
题目描述:
小华从某起点到某目的地需要经过若干次公交转车( 乘车不存在绕圈现象,但不保证可以到达目的地 ),显然坐车的方案可能不唯一。如下图所示,从起点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];
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 ;
______(2)_______
f[0] = true;
b[0] = 0;
cin >> x; //读入目标车站编号
to = x - 'A';
while ( head < tail ) { //广搜:队列不为空,并且没有找到目标车站
c = q[ head ];
______(3)_______
if ( c == to ){ //找到终点
cout << b[c] - 1;
return 0;
}
for ( int j=0; j<n; j++) { //队头的元素,和其他所有的顶点看看有没有边,有则把它拉进队列
if ( ______(4)_______ ) {
q[ tail ] = j;
tail += 1;
f[j] = true;
b[j] = b[c] +1;
}
}
}
printf( "NO PATH!" );
return 0;
}
时间限制: 1000ms空间限制: 256MB
来源: 高中教材