去哪儿-171011笔试题目-请大家分享个解题思路

AC0.8

考虑用最短路径

贴了题，题目限制条件稍多，请高手同学们分享个思路

最短路变形

对于路线l上的点v1,v2,...vm，建图的时候从v1分别指向v2,v3...vm,边权为机票价格c 然后BFS，用一个整数d维护当前经过的目标城市（二进制的方法，最多5个城市） 最多才50个城市，N^4的算法都能跑

从样例中提取数据， from--->to(边权, 优惠机票编号) H--->S(700, 1) B--->S(700, 2) B--->V(700, 2) B--->H(1400, 3) B--->V(1400, 3) 可以看出从Beijing飞往Vancouver有两种价位，第一种直达700，第二种转机1400. 几个问题百思不得姐的问题： 1、那么在记录的时候，是否可以直接记录为其中数值较小的一个，这部分如何处理？ 2、建图的方式和采用的数据结构能否具体阐述一下?，遇到这种节点是String形式的感到无从下手... 3、@有同学认为用BFS，我觉得对于有权图且边权不等的情况，BFS不一定得到最优解吧？需要用Dijkstra... 4、记录机票的使用情况 特来向大家请教！

算法不懂 机械暴力出的哈哈哈 可以看帖