CF601A The Two Routes——Floyd题解

ゞ浴缸里的玫瑰 2023-01-22 12:49 153阅读 0赞

# [【原题目链接：\[CF601A The Two Routes\]（Remote Judge in luogu）】][CF601A The Two Routes_Remote Judge in luogu] #

**题目描述**  
In Absurdistan, there are nn towns (numbered 1 through n ) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y , there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 11 at the same time. They both have the same destination, town n , and don’t make any stops on the way (but they can wait in town nn ). The train can move only along railways and the bus can move only along roads.

You’ve been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n ) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town nn (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town nn at the same moment of time, but are allowed to do so.

**输入格式**  
The first line of the input contains two integers n and m ( 2<=n<=400, 0<=m<=n(n-1)/2) — the number of towns and the number of railways respectively.

Each of the next mm lines contains two integers u and v , denoting a railway between towns u and v ( 1<=u,v<=n, u≠vu).

You may assume that there is at most one railway connecting any two towns.

**输出格式**  
Output one integer — the smallest possible time of the later vehicle’s arrival in town n . If it’s impossible for at least one of the vehicles to reach town n , output -1 .

**题意翻译**  
有个地方有一些城镇，城镇与城镇间有铁路或公路相连，如果有铁路相连，就不会有公路相连，没有铁路连接的城镇就会有公路相连。给你 n 个城镇， m 条铁路线，问同时从城镇1出发，分别坐火车和坐汽车到达城镇n，求两者都到达的时候最少的用时。其中火车和汽车不能同时到达中间点。

**输入格式**  
第一行两个整数 n 和  m ( 0 < = m < = n × ( n − 1 ) / 2 m (0<=m<=n×(n-1)/2 m(0<=m<=n×(n−1)/2表示城镇的数量和铁路的数量。 接下来 mm 行每行两个整数 uu 和 vv ，表示城镇 uu 到 vv 有铁路相连。

**输出格式**  
一个整数，表示两种交通工具都到达终点的最少用时，如果其中有一种交通工具不能到达或都不能到达终点，输出 -1。

相邻两地乘火车或汽车的用时都是1

感谢@UKE自动机 提供的翻译

**输入输出样例**  
输入 \#1复制

4 2
    1 3
    3 4

输出 \#1复制

输入 \#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复制

**说明/提示**  
In the first sample, the train can take the route ![在这里插入图片描述][20210519214648735.png] and the bus can take the route ![在这里插入图片描述][2021051921472019.png]. Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there’s no way for the bus to reach town 4 .

# 题解 #

这道题看n的范围就知道Floyd是可行的。

大致思路是，建立两个邻接矩阵，铁路和公路两个邻接矩阵。初始化将铁路全部赋值为1，公路全部赋值为一个极大值（我们就定义极大值是`#define INF 0xfffffff`）。输入的时候将铁路的1编程INF，公路的INF变成1。然后Floyd中间来两个判断，如果间接路径小于直接路径，就赋值小的就行了。

注意，最后却要输出公路和铁路的最大值，因为铁路和公路两个线路存储的已经是最小值了，但题目要求两个交通工具必须都到达，所以要输出他们中的更大的值。

如何判定-1？如果`int ans = max(map1[1][n], map2[1][n]);`中ans的值是INF，说明至少其中有一个交通工具无法到达终点。所以判断ans==INF就输出-1。

AC的代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    
    #define INF 0xfffffff
    
    using namespace std;
    
    int map1[450][450], map2[450][450];
    
    int main()
    { 
        ios::sync_with_stdio(false);
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                map1[i][j] = INF, map2[i][j] = 1;
        for (int i = 1; i <= m; i++)
        { 
            int x, y;
            cin >> x >> y;
            map1[x][y] = map1[y][x] = 1;
            map2[x][y] = map2[y][x] = INF;
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                { 
                    map1[i][j] = min(map1[k][i] + map1[j][k], map1[i][j]);
                    map2[i][j] = min(map2[k][i] + map2[k][j], map2[i][j]);
                }
        int ans = max(map1[1][n], map2[1][n]);
        if (ans == INF)
            cout << "-1" << endl;
        else
            cout << ans << endl;
        return 0;
    }

[CF601A The Two Routes_Remote Judge in luogu]: https://www.luogu.com.cn/problem/CF601A
[20210519214648735.png]: https://img-blog.csdnimg.cn/20210519214648735.png
[2021051921472019.png]: /images/20221020/616a4ba08d8f4939bb2be6ab15f113e3.png