救命！”王宫的的守卫听到公主的惊呼，推开门冲进去发现恶龙掳走了公主…… 题目描述 骑士回到王国发现公主被恶龙掳走了，骑士知道恶龙的巢穴在山谷 � y 点，而王国的位置在 � x 点。 拯救公主的路上有 � n 个补给点 ( 王国和恶龙巢穴也属于补给点 )， � n 个补给点由 � m 条双向道路连接起来，每条道路上都有一个恶龙的随从，每一个随从的战斗力不一定相同。 骑士虽然很焦急，但是他的战斗力是有限的，在找到恶龙前他并不希望遇到过于强大的敌人损耗自己的实力。所以请你规划一条从 � x 至 � y 的路线，使得经过的道路上的敌人的战斗力最大值最小。 输入格式 第一行有四个用空格隔开的 � n， � m， � x， � y，其含义见【题目描述】。 接下来 � m 行，每行三个整数 � u, � v, � w,表示有一条道路连接补给点 � u 和补给点 � v，且该道路上的敌人战斗力为 � w。 两个补给点之间可能存在多条道路，不同道路上的敌人战斗力也可能不同。 输出格式 输出一行一个整数，代表骑士遇到的敌人中的最高战斗力。 输入输出样例 输入 #1复制 4 6 1 4 1 2 1 2 3 5 3 4 2 1 3 2 1 4 3 2 4 3 输出 #1复制用c++做这道题

这道题目需要使用二分答案来解决。具体思路如下：

1. 定义一个结构体 Edge 表示边，其中包含起点、终点和边权。

2. 定义一个结构体 Node 表示节点，其中包含节点编号和从起点到该节点的最小距离。

3. 定义一个优先队列 q 存储当前还未处理的节点，按节点从小到大排序，每次取出队首元素 u，表示当前到起点距离最短的节点。

4. 遍历节点 u 所有的出边，如果从 u 到 v 的边权 w 加上 u 的距离小于 v 的距离，则更新节点 v 的距离为 u 的距离加上边权 w，并将节点 v 加入队列 q 中。

5. 重复步骤 4 直到队列为空，此时最短路已经求出。

6. 判断最短路中是否存在一条边的边权大于等于当前的二分答案 mid，如果存在，则将该边加入到图中并重新求最短路。

7. 如果最短路的距离小于等于当前的二分答案 mid，则说明可以到达终点，将右边界缩小为 mid，否则将左边界缩小为 mid + 1。

8. 重复步骤 6 和 7 直到左右边界收敛为止，此时的左右边界的值即为答案。

以下是 C++ 代码实现：