酒店官方网站的功能建设,手机免费建设网站制作,网站内容作弊的形式,轻定制网站建设蓝桥杯集训每日一题acwing4074
某国家有 n 个城市#xff08;编号 1∼n#xff09;和 m 条双向铁路。
每条铁路连接两个不同的城市#xff0c;没有两条铁路连接同一对城市。
除了铁路以外#xff0c;该国家还有公路。
对于每对不同的城市 x,y#xff0c;当且仅当它们之… 蓝桥杯集训每日一题acwing4074
某国家有 n 个城市编号 1∼n和 m 条双向铁路。
每条铁路连接两个不同的城市没有两条铁路连接同一对城市。
除了铁路以外该国家还有公路。
对于每对不同的城市 x,y当且仅当它们之间没有铁路时它们之间会存在一条双向公路。
经过每条铁路或公路都需要花费 1 小时的时间。
现在有一列火车和一辆汽车同时离开城市 1它们的目的地都是城市 n。
它们不会在途中停靠但是可以在城市 n 停靠。
火车只能沿铁路行驶汽车只能沿公路行驶。
请你为它们规划行进路线每条路线中可重复经过同一条铁路或公路但是为了避免发生事故火车和汽车不得同时到达同一个城市城市 n除外。
请问在这些条件的约束下两辆车全部到达城市 n 所需的最少小时数即求更慢到达城市 n 的那辆车所需的时间的最小值。
注意两辆车允许但不必要同时到达城市 n。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含两个整数 u,v表示城市 u 和城市 v 之间存在一条铁路。
输出格式
一个整数表示所需的最少小时数。
如果至少有一辆车无法到达城市 n则输出 −1。
数据范围
前 66 个测试点满足 2≤n≤100≤m≤10。 所有测试点满足 2≤n≤4000≤m≤n(n−1)/21≤u,v≤n。
输入样例1
4 2
1 3
3 4输出样例1
2输入样例2
4 6
1 2
1 3
1 4
2 3
2 4
3 4输出样例2
-1输入样例3
5 5
4 2
3 5
4 5
5 1
1 2输出样例3
3 Floyd算法避免被公路铁路的存储误导
参考 http://t.csdn.cn/xfelf
