去哪儿2018校招在线考试-编程题一

发表于 | 分类于 ，

题目 最少转机

描述

去哪儿网将机票业务扩展到了大魏国，
宇文玥和楚乔都是去哪儿网的忠实用户，经常坐飞机双宿双飞，
现在已知大魏国有n个城市，共有m条国内航线，航线都是可往返的，
已知他们所居住的城市和他们想要达到的城市，请给出最小转机次数。
如果两城市间不可到达，则返回DISCONNECTED

输入

第一行两个数n，m（2≤n≤100，1≤m≤100） ; 
紧随其后的是两个城市的名称，代表居住城市和想要到达的城市
接下来m行，分别为各个航线间的两个城市（城市名称间以空格隔开）

输出

输出最少转机次数

Example

Input

5 5 LuoYang JinLing
ChangAn LuoYang
LuoYang JianKang
LuoYang LangYe
JianKang LangYe
JianKang JinLing

Output

2

题解

广度优先搜索

  • 使用邻接矩阵存储机票
  • 因为只需要计算转机数,所以计边的权重为 1
  • 所有边的权重相同,则可采用 BFS 解决最短路问题
  • 时间复杂度 O(n),空间复杂度 O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

#define ll long long
using namespace std;

int n,m,orgC,desC;
string org,des;
map<string,int>city;
bool route[105][105];
int minDis[105];
bool vis[105];

void minDistance()
{
    queue<int> cQueue;
    cQueue.push(orgC);
    int now;
    while(cQueue.size())
    {
        now=cQueue.front();
        if(now==desC)return ;
        cQueue.pop();
        vis[now]=1;
        for(int i=0;i<n;++i)
        {
            if(route[now][i]&&!vis[i])
            {
                cQueue.push(i);
                minDis[i]=minDis[now]+1;
            }
        }
    }
}

int main()
{

    memset(route,0,sizeof route);
    memset(minDis,0,sizeof minDis);
    memset(vis,0,sizeof vis);

    string tmp1,tmp2;
    int cIndex=0,tmpI1,tmpI2;

    cin>>n>>m>>org>>des;

    while(m--)
    {
        cin>>tmp1>>tmp2;
        if(!city.count(tmp1))
            city[tmp1]=cIndex++;
        if(!city.count(tmp2))
            city[tmp2]=cIndex++;
        tmpI1=city[tmp1],tmpI2=city[tmp2];
        route[tmpI1][tmpI2]=1;
        route[tmpI2][tmpI1]=1;
    }

    orgC=city[org],desC=city[des];

    minDistance();

    if(minDis[desC])
        cout<<minDis[desC];
    else
        cout<<"DISCONNECTED";

}