阿里巴巴笔试4/20 实习生

题目很简单，第一题很快就过了，第二道题过了百分之60，应该是算法不够优化，但是第二题的基本思路就是图的BFS搜索，我现在回想起来，可优化的地方就是“怎么选取城市”这里了。

把题目大致描述出来，供大家参考。如果题目描述错了，希望大家指正！😊 #

1. 勇士打怪兽

勇士打怪兽，勇士有一个初始能力值，记为 a ,怪兽有 n 个，每个怪兽有自己的能力值，记为 i 。当 a>=i时，勇士可以打败怪兽，并获得一枚金币。且勇士在任意时刻都可以选择花费一枚金币提升自己1点能力值。
勇士打怪兽的顺序随意，勇士的初始金币为0.

问：
勇士最大可以获得多少金币，怪兽不一定要打完。

输入：
第一行：勇士能力值 a ，怪兽个数 n
第二行：n个数，分别代表怪兽的能力值。

2. 最短路径

有n个城市，每个城市有自己的等级level，城市之间有n-1条路径。
小明可以选择任意的level相同的城市作为起点和终点，并从起点走到终点。
问：
小明走路的最短距离是多少？

输入：
第一行：城市个数 n
第二行：n个数，分别代表不同的城市的level
下面n-1行：每一行有两个数，记为 x y，代表 x 到 y 有路