一 原问题链接

1797 -- Heavy Transportation

http://poj.org/problem?id=1797

二输入和输出

1 输入

第1行包含测试用例数量。每个测试用例的第1行都包含 n和m，分别表示街道交叉口的数量和角度的数量。以下 m 行，每行都包含3个整数，分别表示街道的开始、结束和承重。在每对交叉点之间最多有一个条街道。

2 输出

对每个测试用例，输出都以包含“Scenario #i:”行开头，其中 i 是从 1 开始的测试用例编号。然后单行输出可以运输给客户的最大承重。在测试用例之间有一个空行。

三 输入和输出样例

1 输入样例

1

3 3

1 2 3

1 3 4

2 3 5

2 输出样例

Scenario #1:

4

四 分析

本问题要求找到一条通路，是最小边权最大的通路，该通路的最小边权即最大承重。

如下图所示，从节点1到节点6有3条通路，其中1-2-4-6 的最小边权为3,1-3-4-6 的最小边权为4,1-3-5-6 的最小边权为2；最小边权最大的通路为1-3-4-6，该通路的最大承重为4，超过4则无法承受。

五 算法设计

1 将所有的街道都采用链式前向星存储，每个街道都是双向的。

2 将 Dijkstra 算法的更新条件变形一下，改为最小值最大的更新。

六 代码

package graph.poj1797;

import javafx.util.Pair;

import java.util.PriorityQueue;
import java.util.Scanner;

public class POJ1797 {
    static final int maxn = 1005;
    static final int maxe = 1000001;
    static final int inf = 0x3f3f3f3f;
    static int T;
    static int n;
    static int m;
    static int w;
    static int cnt;
    static int head[] = new int[maxn];
    static int dis[] = new int[maxn];
    static Edge e[] = new Edge[maxe];
    // 标记是否已访问
    static boolean vis[] = new boolean[maxn];

    static {

        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }

        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0;
        }
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v, int w) {
        e[cnt].to = v;
        e[cnt].next = head[u];
        e[cnt].w = w;
        head[u] = cnt++;
    }

    // dijkstra 算法变形，求最小值最大的路径
    static void solve(int u) {
        PriorityQueue<MyPair<Integer, Integer>> q = new PriorityQueue<>();
        dis[u] = inf;
        MyPair pair = new MyPair(dis[u], u);
        q.add(pair); // 最大值优先
        while (!q.isEmpty()) {
            int x = (int) q.peek().getValue();
            q.poll();
            if (vis[x])
                continue;
            vis[x] = true;
            if (vis[n])
                return;
            for (int i = head[x]; i >= 0; i = e[i].next) {
                int v = e[i].to;
                if (vis[v])
                    continue;
                if (dis[v] < Math.min(dis[x], e[i].w)) { // 求最小值最大的
                    dis[v] = Math.min(dis[x], e[i].w);
                    q.add(new MyPair(dis[v], v));
                }
            }
        }
    }

    public static void main(String[] args) {
        int p = 1;
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();

        while (T-- > 0) {
            cnt = 0;
            for (int i = 0; i < head.length; i++) {
                head[i] = -1;
            }
            n = scanner.nextInt();
            m = scanner.nextInt();

            int u, v, w;
            for (int i = 1; i <= m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                w = scanner.nextInt();

                add(u, v, w);//两条边
                add(v, u, w);
            }
            solve(1);
            System.out.println("Scenario #" + p++ + ":");
            System.out.println(dis[n]);
            System.out.println();
        }
    }
}

class Edge {
    int to;
    int w;
    int next;
}

class MyPair<K, V> extends Pair implements Comparable {

    /**
     * Creates a new pair
     *
     * @param key   The key for this pair
     * @param value The value to use for this pair
     */
    public MyPair(Object key, Object value) {
        super(key, value);
    }

    @Override
    public int compareTo(Object pair) {
        if ((Integer) this.getKey() > (Integer) (((Pair) pair).getKey())) {
            return 1;
        } else if ((Integer) this.getKey() < (Integer) (((Pair) pair).getKey())) {
            return -1;
        } else {
            return 0;
        }
    }
}

七 测试

绿色为输入，白色为输出

八 参考

线程"main“java.lang.ClassCastException中出现异常: javafx.util.Pair不能强制转换为java.lang.Comparable - 问答 - 腾讯云开发者社区-腾讯云另外，这个问题已经问了很多次了，我无法根据我的解决方案来解决这个问题。我正在编写加权图的Dijkstra算法。我使用ArrayList>>来存储我的权重和边。在实现Dijkstra函数时，我使用了M...

https://cloud.tencent.com/developer/ask/sof/1269961