解题思路

1. 问题转化

   • 该问题可以转化为图的“最大瓶颈路径”问题（Maximum Bottleneck Path），即在所有路径中，寻找一条路径，使得路径上的最小边权最大。
   • 类似于最短路径问题，但优化目标不同。

2. 算法选择

   • Dijkstra 算法的变种：
     • 普通 Dijkstra 用于求最短路径，这里改为维护路径上的最小边权，并优先扩展当前最小边权最大的路径。
   • Kruskal 算法（最大生成树思想）：
     • 按边权从大到小排序，用并查集（Union-Find）逐步合并边，直到起点和终点连通，此时最后加入的边的权值即为答案。

3. 推荐方法：Modified Dijkstra（优先队列优化）

   • 使用优先队列（最大堆），存储 (当前路径的最小边权, 当前节点)。
   • 维护一个数组 max_min[]，记录到达每个节点时的最大可能最小边权。
   • 每次从队列中取出当前最优的路径（即 min_edge 最大的），并尝试更新邻居节点的 max_min。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <climits>
using namespace std;

int main() {
    int n, r, tc = 1;
    while (cin >> n >> r, n || r) {
        map<string, int> city_idx;  // 城市名 -> 编号
        vector<vector<pair<int, int> > > adj(n); // 邻接表：pair<邻居, 载重限制>
        int idx = 0;

        // 输入道路信息，构建图
        for (int i = 0; i < r; i++) {
            string u, v;
            int w;
            cin >> u >> v >> w;
            if (city_idx.find(u) == city_idx.end()) city_idx[u] = idx++;
            if (city_idx.find(v) == city_idx.end()) city_idx[v] = idx++;
            adj[city_idx[u]].push_back(make_pair(city_idx[v], w));
            adj[city_idx[v]].push_back(make_pair(city_idx[u], w));
        }

        string start, dest;
        cin >> start >> dest;
        int s = city_idx[start], d = city_idx[dest];

        // Modified Dijkstra：优先队列按 min_edge 从大到小排序
        priority_queue<pair<int, int> > pq;  // pair<min_edge, current_node>
        vector<int> max_min(n, -1);  // 记录到达每个节点的最大 min_edge
        pq.push(make_pair(INT_MAX, s));
        max_min[s] = INT_MAX;

        while (!pq.empty()) {
            pair<int, int> top = pq.top();
            pq.pop();
            int current_min = top.first;
            int u = top.second;
            if (u == d) break;  // 到达终点，可以提前退出
            if (current_min < max_min[u]) continue;  // 非更优路径，跳过

            for (size_t i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i].first;
                int w = adj[u][i].second;
                int new_min = min(current_min, w);  // 更新路径上的最小边权
                if (new_min > max_min[v]) {  // 找到更优路径
                    max_min[v] = new_min;
                    pq.push(make_pair(new_min, v));
                }
            }
        }

        cout << "Scenario #" << tc++ << "\n";
        cout << max_min[d] << " tons\n\n";
    }
    return 0;
}