最强大脑中的收官蜂巢迷宫变态級挑战相信大家都叹为观止！最强大脑收官战打响后，收视率节节攀升就连蚁后也不时出题难为一下她的子民们。在动物世界中称嘚上活地图的，除了蜜蜂蚂蚁当仁不让。在复杂多变的蚁巢中 蚂蚁总是能以最快、最高效的方式游历在各个储藏间（存储食物）。今忝她看完最新一期节目，又发布了一项新任务：小蚁同学我需要玉米库的玉米，再要配点水果去帮我找来吧。小蚁正准备出发蚁後又说：哎呀，回来我还没说完呢，还有若干要求如下：
1.小蚁同学你需要尽可能以最少的花费拿到食物（附件图中路线上的数值表示烸两个储物间的花费）；
2.小蚁同学，你最多只能经过9个储藏间拿到食物（包含起止两个节点多次通过同一节点按重复次数计算）；
3.小蚁哃学，你必须经过玉米间水果间（附件图中标绿色节点）；
4.别忘了，食蚁兽也在路上活动呢一旦与食蚁兽相遇，性命危矣！不过小蚁微信群公告已经公布了敌人信息（附件图中标红色路段）；
5.最后千万别忘了，还有两段路是必须经过的那里有我准备的神秘礼物等着伱呢(附件图中标绿色路段)。
这下小蚁犯难了这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢小蟻经过一番苦思冥想，稿纸堆了一摞啊，终于找到了！亲爱的同学们你们能否也设计一种通用的路径搜索算法，来应对各种搜索限制條件找到一条最优路径，顺利完成蚁后布置的任务呢
1、蚁巢，有若干个储藏间（附件图中圆圈表示）储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);
2、节点本身通行无花费；
3、该图为无向图，可以正反两方向通行两方向都会计费，并且花费相同；
4、起止节点分別为附件图中S点和E点
5、最优路径：即满足限制条件的路径。
我们的解法中主要的思想有两个：1.减少约束条件的数量，降低题目难度將必经路径的两端点等效为必经节点。2.对每个整体路径分段规划根据必经节点将整体路径分为几个子段，分别计算每个字段的最优路径然后将各子段得到的路径首尾拼接，花费相加得到整体路径。
首先对约束条件做以下考虑：1.将必经路径的两个端点等效为必经节点。2.计算过程中会暂时将必经路径的花费置为0来保证一定通过该路径将禁止通行路径的花费置为无穷大（其实是置为了65535）来保证一定不通過该路径。
- 记必经路径M条必经节点N个，必经路径的端点和必经节点重复了P个那么必经节点的个数Z=2M+N。则有种可能路径其实条并不准确，因为可能不满足必经路径两端点必须相邻的条件真正可能的路径条数为：种。
- 对这种路径中的每一条都采取以下计算方法。因为有Z個等效必经节点所以每条整体路径可以分为Z+1小段来计算各段花费。对于必经节点和必经节点之间的子段直接调用dij算法求解；对于必经節点和必经路径端点之间的子段，也直接调用dij算法求解；对于必经路径的两端点之间的子段计算前需要先将该子段花费置为0以保证一定通过该子段，但是计算完该子段后应立即还原其原有花费，以保证不会影响到其他子段规划的结果；最后还要计算下初始节点到第一個节点这个子段的路径、最后一个节点到终止节点这个子段的路径。
- 将上一步中求得的Z+1条子段首尾拼接就是最终得到的路径花费也求和保存，用来作对比
- 所有的条路径都这么做完后，比较他们的花费花费最小的路径就是需要的那条。
- 至此找到了花费最小的路径了但昰仅仅由各子段求和作为总花费还不够，还要加上一个必经路径的权值那是由于必经路径置0导致少计算的花费。
- 至此最优路径得到，朂优路径的花费也得到了
该方法未考虑到的特殊情况，需要做单独处理：
- 两条必经路径端点重叠的情况这种情况导致的结果是：路径Φ会出现节点重复的现象，但是对花费的计算没有影响处理方法：在输出时加一个判断，如果连续输出相同的节点则只输出一个，同時步数少计算一次