M6 米乐M6 米乐你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费「体力」最小的一条路径。

　　事实上，当题目允许往任意方向移动时，考察的往往就不是 DP 了，而是图论。

　　那为什么有一些 DP 题目简单修改条件后，就只能彻底转化为图论问题来解决了呢？

　　这是因为修改条件后，导致我们 DP 状态展开不再是一个拓扑序列，也就是我们的图不再是一个拓扑图。

　　当一道题我们决定往「图论」方向思考时，我们的重点应该放在「如何建图」上。

　　因为解决某个特定的图论问题（最短路/最小生成树/二分图匹配），我们都是使用特定的算法。

　　由于使用到的算法都有固定模板，因此编码难度很低，而「如何建图」的思维难度则很高。

　　因为在任意格子可以往「任意方向」移动，所以相邻的格子之间存在一条无向边。

　　存储的格式为数组[a, b, w]，代表编号为a的点和编号为b的点之间的权重为w。

　　当我们有了所有排好序的候选边集合之后，我们可以对边进行从前往后处理，每次加入一条边之后，使用并查集来查询「起点」和「终点」是否连通（并查集部分）。

　　当第一次判断「起点」和「终点」联通时，说明我们「最短路径」的所有边都已经应用到并查集上了，而且由于我们的边是按照「从小到大」进行排序，因此最后一条添加的边就是「最短路径」上权重最大的边。

　　// edge 存的是 [a, b, w]：代表从 a 到 b 的体力值为 w

　　// 虽然我们可以往四个方向移动，但是只要对于每个点都添加「向右」和「向下」两条边的话，其实就已经覆盖了所有边了

　　// 从「小边」开始添加，当某一条边别应用之后，恰好使用得「起点」和「结点」联通

　　我们之所以能够这么做，是因为「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是w最大的边」。

　　我们先假设「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是w最大的边」不成立：

　　这是我们「刷穿 LeetCode」系列文章的第No.1631篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

　　在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

　　为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：e/LogicStack-LeetCode。

　　在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。