米乐M6 M6米乐米乐M6 M6米乐祖传的手艺不想丢了，所以按顺序写一个leetcode的题解。计划每日两题，争取不卡题吧。
由于题目中的最小体力消耗指的是路径上所有边消耗的最大值，那么可以明确的一点是，当最小体力消耗越大时，每个点能走的相邻点就越多，换言之就是越有可能从起点走到终点。
那么一个自然的想法就是直接二分答案，然后从起点开始进行bfs，并根据能否走到终点来调整二分的边界。
当然，由于这里路径的权重都非负，且满足三角形不等式，那么在这里使用dijkstra算法也是可行的。由于题目边的规模是O(mn)的，因此使用dijkstra的时间复杂度应该比二分答案的时间复杂度稍微好点。
2022-10-20 03:26:14
浏览次数：
次
返回列表
