C++最少换乘汽车问题求解
题目描述
小马与小张准备一同出去旅游，交通工具选择长途大巴车，他们目前所在城市编号为c，目标城市编号为d，没有直接从城市c到城市d(d<=100)的大巴车，需要换乘大巴，根据信息计算出最少的换乘次数。备注：每一辆长途大巴行车路线中不会经过另一个城市。
输入
第一行，a,b,c,d四个整数，a表示城市数量，b表示公路数量，c表示起点城市，d表示终点城市
b行公路信息，每一行m，n两个整数，分别表示公路连接的两个城市编号。
输出
最少换乘次数
样例输入1
5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5
样例输出1
2
广搜就可以很好的解决呀。广搜的基本思想就是一条路走到底，看看能不能到终点。每次遇到“分叉路口”时——即从一个结点可以到多个结点的时候，用队列一一记录下各个结点的值，然后选一条路走，不能就回到上一级的“分叉路口”，以此类推。不断记录可以到达终点的最小值，得出结构。这样讲有点抽象，建议看些博客学习一下。