题目描述(ID:12038)
标题: 最少转机
标签: 搜索 广度优先搜索
详情:

小哼和小哈一同坐飞机去旅游,他们现在位于1号城市目标是5号城市,可是1号城市并没有到5号城市的直航不过小哼已经收集了很多航班的信息,现在小哼希望找到一种乘坐方式,使得转机的次数最少,如何解决呢?

输入格式:
第一行的有两个整数n m s e,n表示有n个城市(城市编号为1~n),m表示有m条航线,s表示起点城市,e表示目标城市。
接下来m行每行是一条类似“a b”这样的数据表示城市a和城市b之间有航线,也就是说城市a和城市b之间可以相互到达
输出格式:
s号城市到e号目标城市,需要飞行几次?
限制: 1<=n<=1000
1<=m<=300000
样例:

输入

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

输出

2
登录并解答