登录 注册
最少转机： 去哪儿网将机票业务扩展到了大魏国，宇文玥和楚乔都是去哪儿网的忠实用户，经常坐飞机双宿双飞，现在已知大魏国有n个城市，共有m条国内航线，航线都是可往返的，已知他们所居住的城市和他们想要达到的城市，请给出最小转机次数。如果两城市间不可到达，则返回DISCONNECTED 输入 第一行两个数n，m（2≤n≤100，1≤m≤100） ; 紧随其后的是两个城市的名称，代表居住城市和想要到达的城市 接下来m行，分别为各个航线间的两个城市（城市名称间以空格隔开） 输出 输出最少转机次数 样例输入 5 5 LuoYang JinLing ChangAn LuoYang LuoYang JianKang LuoYang LangYe JianKang LangYe JianKang JinLing 样例输出 2
作图的问题首先我们应该用邻接矩阵或者二维数组来存取顶点之间的关系。
广度优先搜索需要用队列来存储每次扩展的关系。
首先将1号城市入队，通过1号城市我们可以扩展出2号和3号城市，2号城市又可以扩展出3号城市和4号城市。由于3号城市已经在队列中，所以只需要将四号城市入队。
接下来3号城市又可以扩展处4号城市和5号城市，因为4号城市已经在队列中，所以只需要将5号城市入队。此时已经找到5号城市，那么算法结束。
isaimawang
@ 赛码网
533869549