2017去哪儿笔试（软开）

1同学们，我们刚刚经历了十一和中秋双节假期，让我们一起预祝我们的祖国繁荣富强，同学们每个中秋与家人共赏明月，也期待同学们能够加入去哪儿网，为大家的出游和回家团圆尽一份力量。
我们的第二题是这样的，给出一个以空格作为分隔符的字符串，求其与其空格分隔的逆序字符串的最长公共子序列长度。
输入
例如：输入 2017 11 02
其逆序字符串为 02 11 2017
输出
6(2 11 2)

样例输入
2017 11 02
样例输出
6


一张机票的价格是由多个因素决定的，它通常与飞行距离没有直接的关系。许多旅行者于是在这方面变得非常有创意，当飞机在多个城市停靠时，只是用机票的一部分，以实现低花费的旅行。例如：北京到温哥华的机票可能卖8000元人民币，但是，北京-温哥华-西雅图的机票可能卖7500元，如果用户的目的地是温哥华，那么用户会选择买北京-温哥华-西雅图的机票，当他乘坐完北京-温哥华的航段后，会放弃乘坐温哥华到西雅图的航段。然而，航空公司也了解这种行为，并通常要求一张机票所包含的站点必须要按顺序旅行，而且不允许中途加入其他路线。例如：你手中有一张从北京到温哥华然后再到西雅图的机票，你不能仅使用机票中温哥华到西雅图的部分，你必须从机票上的第一个城市北京出发；此外，也不允许你从城市北京到城市温哥华，然后去一些其他地方如多伦多并返回温哥华，再继续你从温哥华到西雅图的旅途。
给出一组优惠的机票，以及一条或多条旅游路线，你要确定为了使旅行费用最少，应该如何购买机票。
现假设：优惠机票航线不多于10条，每组优惠机票的测试用例旅行路线不多于10条，每张机票的航段数不多于5个，每个优惠航线票价不高于10000元
输入
包含一组测试用例，测试用例中描述一组优惠机票和一组旅行路线
每组测试用例由4部分组成：
第1行为优惠机票航线有多少条（n）
第2行~第2+n-1行描述优惠机票编号，每张优惠机票的价格、航段数和航段顺序
第2+n行描述了测试用例的旅行路线
输出
对于每条旅行路线，输出两行，包括测试用例编号、路线编号、路线的最小花费；然后按使用顺序输出本次旅行所使用的机票编号，具体输出格式见样例，保证答案唯一。如果输入参数不合法，则返回Error。

样例输入
3
1 700 2 HongKong Seattle
2 700 3 Beijing Seattle Vancouver
3 1400 3 Beijing HongKong Vancouver
3 Beijing HongKong Seattle
样例输出
2100
3 1

3.最少转机：
去哪儿网将机票业务扩展到了大魏国，宇文玥和楚乔都是去哪儿网的忠实用户，经常坐飞机双宿双飞，现在已知大魏国有n个城市，共有m条国内航线，航线都是可往返的，已知他们所居住的城市和他们想要达到的城市，请给出最小转机次数。如果两城市间不可到达，则返回DISCONNECTED
输入
第一行两个数n，m（2≤n≤100，1≤m≤100） ; 紧随其后的是两个城市的名称，代表居住城市和想要到达的城市
接下来m行，分别为各个航线间的两个城市（城市名称间以空格隔开）
输出
输出最少转机次数

样例输入
5 5 LuoYang JinLing
ChangAn LuoYang
LuoYang JianKang
LuoYang LangYe
JianKang LangYe
JianKang JinLing
样例输出
2

 参考