acwing4074. 铁路与公路

题目

某国家有n个城市（编号1∼n）和 m条双向铁路。

每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。

除了铁路以外，该国家还有公路。

对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。

经过每条铁路或公路都需要花费 1 小时的时间。

现在有一列火车和一辆汽车同时离开城市 1，它们的目的地都是城市 n。

它们不会在途中停靠（但是可以在城市 n停靠）。

火车只能沿铁路行驶，汽车只能沿公路行驶。

请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n 除外）。

请问，在这些条件的约束下，两辆车全部到达城市 n所需的最少小时数，即求更慢到达城市 n的那辆车所需的时间的最小值。

注意，两辆车允许但不必要同时到达城市 n。

题解

从1号到n号点由于没有铁路的话必然存在公路，所以1-n号点的最短时间肯定为1，那么就只需要考虑另外一条线路的最短时间了。用两个floyd即可。

#include<iostream>
#include<cstring>
using namespace std;
const int N=410;
int g[N][N],f[N][N];
int n,m;
int floyd(int d[][N]){
    if(d[1][n]==1)return 1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
    return d[1][n];
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    memset(f,0x3f,sizeof f);
    while(m--){
        int x,y;
        cin>>x>>y;
        g[y][x]=g[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&g[i][j]!=1)
                f[i][j]=1;
    int a=floyd(f),b=floyd(g);
    int ans=max(a,b);
    if(ans!=0x3f3f3f3f)cout<<ans<<endl;
    else cout<<-1<<endl;
    
    return 0;
}