题目描述

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

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

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

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

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

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

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

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

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

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

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

样例

4 2
1 3
3 4

算法1

(暴力枚举) $O(n^2)$

思路： 如果不是铁路就是公路 ,所以 有一种车只需1就能达到

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
bool a[444][444],b[444];
int lja[444444],ljb[444444];
int dfs(int c){
    queue<pair<int,int> >p;
    p.push(make_pair(1,0));
    b[1]=1;
    while(p.size()){
        int x=p.front().first;
        int y=p.front().second;
        p.pop();
        if(x==n){
            return y;
        }
        for(int i=1;i<=n;i++){
            if(a[x][i]==c&&b[i]==0){
                p.push(make_pair(i,y+1));
                b[i]=1;
            }
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        a[x][y]=true;
        a[y][x]=true;
    }
    if(a[1][n]==0){
        cout<<dfs(1);
    }
    else cout<<dfs(0);
}