【C++竞赛 E】xxx和yyy的旅行

时间限制：1s 内存限制：32MB

问题描述

有n个城市和m条双向铁路。对于任意两个不同的城市x和城市y，两个城市之间有双向铁路，否则有双向公路，通过任意一条直达公（铁）路花费一小时。城市x与城市y存在直达公（铁）路：乘坐汽（火）车可以从城市x到达城市y且中间不经过其它城市

一辆汽车和一辆火车停在城市1，它们有相同的目的地城市n。汽车只能走公路，火车只能走铁路。为了避免车祸的发生，汽车和火车不能在同一时间到达同一个城市（目的地城市n除外）。

现在xxx和yyy在城市1，他们想去城市n，xxx乘坐火车而yyy乘坐汽车。请你为他们规划路线，使得他们到达城市n所花费的时间T=max?(T_xxx,T_yyy)最小。

输入描述

第一行一个整数T(1≤T≤10)表示数据组数。

对于每组数据，第一行两个整数n(2≤n≤100),m(0≤m≤n(n-1)/2),接下来m行，每行两个整数u,v(1≤u,v≤n)，表示城市u和城市v之间有一条双向铁路。

数据保证同一条铁路只会出现一次。

输出描述

对于每组数据，输出一行，如果xxx和yyy可以到达城市n，输出他们花费的最小时间，否则输出-1。

输入样例

1

4 3

1 3

1 4

2 4

输出样例

3

样例解释

样例如下图所示，其中铁路为实线，公路为虚线



xxx坐火车可从城市1直达城市4花费1小时

yyy坐汽车走1—2—3—4花费3小时

【题目链接】:

【题解】



铁路图上如果有从1-n的直接路径,就在公路图上做最短路；

否则在铁路图上做最短路；

因为有从1-n的直接路径的话，肯定走那条路最优;然后另外一个人怎么走都可以了；因为不会撞在一起(撞在n号节点是允许的);



【完整代码】

#include <bits/stdc++.h>

#define rep1(i,a,b) for (int i = a;i <= b;i++)

using namespace std;

#define pb push_back;

const int MAXN = 100+10;

const int INF = 0x3f3f3f3f;

bool bo[MAXN][MAXN];

vector <int> g[3][MAXN];

int dis[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while (T--)

    {

        memset(bo,false,sizeof(bo));

        int n,m;

        scanf("%d%d",&n,&m);

        rep1(j,1,n)

            g[1][j].clear(),g[2][j].clear();

        rep1(i,1,m)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            g[1][x].push_back(y);

            g[1][y].push_back(x);

            bo[x][y] = true;

            bo[y][x] = true;

        }

        rep1(i,1,n)

            rep1(j,1,n)

                if (i!=j)

                    if (!bo[i][j])

                        g[2][i].push_back(j);

        int t=1;

        if (bo[1][n])

            t = 2;

        memset(dis,INF,sizeof(dis));

        dis[1] = 0;

        queue <int> dl;

        dl.push(1);

        while (!dl.empty())

        {

            int x = dl.front();

            int len = g[t][x].size();

            dl.pop();

            rep1(i,0,len-1)

            {

                int y = g[t][x][i];

                if (dis[y] > dis[x]+1)

                {

                    dis[y] = dis[x]+1;

                    dl.push(y);

                }

            }

        }

        if (dis[n]>=INF)

            puts("-1");

        else

            printf("%d\n",dis[n]);

    }

    return 0;

}