codeforces #333 div 2 C. The Two Routes

2015年12月22日 0 作者 CrazyKK

http://codeforces.com/problemset/problem/602/C
题意:给出n个城镇,m条双向铁路,对于任意不同的x,y,如果x,y之间没有铁路,那么一定有双向公路。train只能走铁路,bus只能走公路。现在一辆火车和一辆bus同时从1出发,要到达n,处于安全考虑,bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达,那么输出-1.
思路:n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意,一定存在一条1到n的路,不是公路就是铁路。那么就让有路的花费1的代价到n,然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。