苏盈文 刘佳园 张向远

（1、兰州理工大学理学院，甘肃 兰州 730050 2、兰州理工大学机电工程学院，甘肃 兰州 730050 3、兰州理工大学计算机与通信学院，甘肃 兰州 730050）

1 模型建立与求解

1.1 针对第一关

首先将地图转化为点和线组成的无向图[1]，如图1 所示。其中，“1”为起点，“13”为终点。接着利用Dijkstra 算法[2，3]对从起点到矿山、矿山到终点和起点到终点的最短路径求解。

图1 第一关路径无向图

观察分析可得出起点到矿山和起点到终点的最短路径都是需行走三天，因为前三天整个地图的天气一样，所以从起点去矿山或者直接去终点所消耗的资源一样。因此只需要计算方案二到达矿山后挖矿赚取的收益与从矿山到达终点消耗资源金额的对比，从而确定最优策略。

假设方案二到矿山后的7 天全部为晴朗，计算所得的收益与消耗之间的关系如下：

其中Bw1为行走时所消耗的水；Bf1为行走时所消耗的食物；Bw2为在矿山所消耗的水；Bf2为在矿山所消耗的食物；ω 为花费金额。

1.2 针对第二关

首先，从起点到村庄，走其最短路径。通过计算发现在前四步跨区域的行程中，无论经历的沙暴是0 天还是9 天，都要回村庄补给完毕后再去挖矿所得经济效益最高。所以无论沙暴出现在哪一天，从起点出发的第一步都是都是前往村庄。在到达村庄前，最坏的情况为遭遇9 天沙暴且行进时为高温天气，所以在起点要备足经历9 天沙暴和5 天高温行程的水和食物，又要保证在村庄补给所花费的资金最少，因此带到的村庄的极限水量，剩余容量全部带食物，以尽量减少食物在村庄的购买，即在起点所购资源为180 箱水和330 箱食物。……