30世纪，X同学领悟了通天大道，开始在各个星球之间穿梭。但因为每次穿梭需要消耗巨大的能量，X同学只好暂时放弃了宇宙遨游的梦想。10年后，他发现每个星球之间的穿梭通道其实隐含着巨大的能量可供飞行，由于X同学天赋异禀，顿悟了吸星大法，他很快踏上了他的宇宙之旅。

X同学从地球（1号星球）出发，准备前往遥远的n号星球。因为有强大的力量束缚X同学的能力，X同学只能见到n个星球（1号到n号），且只能在他能力范围内的m个穿梭通道内通行，并用他顿悟的吸星大法吸取其中的全部或部分能量。两个星球之间有且只有一个穿梭通道。

由于穿梭通道的能量能给X同学带来难以言喻的爽快感，X同学希望自己在能到达n号星球的所有穿梭通道内，每次获得的能量尽可能大。遗憾的是，吸星大法是很容易走火入魔的。如果X同学在路途中的某一个通道内获得过大的能量，且在接下来的路途中，有通道无法提供与之相等的能量，X同学将倍感空虚，进而损伤道基，这显然是不能被X同学所接受的。当然，X同学也不会选择吸收大于前面任何通道吸收的能量，这将可能导致他爆体而亡。换句话说，X同学每次吸收的能量全部相同。所以，X同学必须提前做好功课，确定好每次能获得的最大能量。

Input

题目有多组测试数据。

第一行给一个 T。

每一组数据的第一行给两个数n和m，表示X同学能见的n个星球和能通行的m个穿梭通道。
（1 <= n <= 1000）

接下来m行，每行三个数s1，s2，d代表两个星球的编号和它们之间穿梭通道隐含的全部能量。
（1 <= s1，s2 <= n ， 1 <= d <= 1e6）

Output

每组数据先输出一行 Scenario #k，其中 k 是组别编号（从 1 开始）。

下一行输出一个整数，表示X同学每次能获得的最大能量。

最后输出一个空行。

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4

思路 1

通过dijkstra，利用优先队列因为本题是求最大化到达终点路径中能吸收的最小能量，所以优先队列就用它默认的大顶堆即可，将dis[i]放入第一个值，顶点编号放入第二个值，

code 1

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 +5;
const int limit = 1e6 + 5;
int dis[N];//最大化到达终点路径中能吸收的最小能量
bool vis[N];
int n, m;
int e[N][N];
void dijkstra(){
    for (int i = 0; i <= n; ++i) {
        dis[i] = -limit;
        vis[i] = false;
    }
    int num = 0;
    priority_queue<pii> pq;//第一个存dis  第二个值存点
    dis[1] = limit;
    pq.push(pii(limit, 1));
    while(pq.size() && num <= n){
        int u = pq.top().second;
        pq.pop();//在top完 立马pop避免出现死循环
        if(vis[u]) continue;
        vis[u] = true;
        num++;
        for (int i = 1; i <= n; ++i) {
            if(e[u][i] != -1 && !vis[i]){
                dis[i] = max(dis[i], min(dis[u], e[u][i]));
                pq.push(pii(dis[i], i));
            }
        }
    }
}
int main() {
    int t;
    cin >> t;
    int k = 0;
    while(t--){
        cin >> n >> m;
        for (int i = 0; i < N - 1; ++i) 
            for (int j = i + 1; j < N; ++j) 
                e[i][j] = e[j][i] = -1;

        for (int i = 1; i <= m; ++i) {
            int x, y, d;
            cin >> x >> y >> d;
            e[x][y] = e[y][x] = d;
        }
        dijkstra();
        printf("Scenario #%d:\n", ++k);
        printf("%d\n\n", dis[n]);
    }
    return 0;
}

思路 2

Edge重载了<运算符，规定权值较大的边比较小，而sort函数是默认从小到大排 sort之后边的顺序其实是按权值从大到小

利用最大生成树保证生成 最小边权值最大的那一条路径，因为生成过程中，边的权值顺序是从大到小的，所以能使从结点1至结点n连通的最后一条边就是题目所求的最小边 只要结点1到结点n有通路就可以跳出，不要生成整棵树。

code 2

//
// Created by 33744 on 2024/7/25.
//
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3 +5;
const int M = 5e5;
struct Edge{
    int from;
    int to;
    int d;
    //对edge排序 重载
    bool operator < (const Edge& t)const{
        return d > t.d;
    }
}edge[M];
int pre[N];
int find(int x){
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
int main() {
#ifdef ACM_LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    int t;
    cin >> t;
    int k = 0;
    while(t--){
        int n, m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i <= n; ++i) {
            pre[i] = i;
        }

        for (int i = 1; i <= m; ++i) {
            int x, y;
            int d;
            scanf("%d%d%d",&x,&y,&d);
            edge[i].from = x;
            edge[i].to = y;
            edge[i].d = d;
        }
        //对edge里的d实现升序排序
        sort(edge + 1, edge + 1 + m);
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            Edge &e = edge[i];
            int x = find(e.from);
            int y = find(e.to);
            if(find(1) != find(n)){//1号星球和n号星球未联通
                ans = e.d;
                pre[x] = y;
            }
            else{
                break;//找到直接退出
            }
        }
        printf("Scenario #%d:\n", ++k);
        printf("%d\n\n", ans);

    }
    return 0;
}