There are m undirected edges on the map, Each edge (x, y, w) represents the weight of positionxto positionyisw. There may be multiple paths from position0to positionn. We define the risk value of a path as the maximum weight of all the edges in this path.
What is the smallest risk value in all paths from position0to positionn?

Have you met this question in a real interview?

Yes

Example

Give n =2, m =2, x =[0, 1], y =[1, 2], w =[1, 2], return2.

Explanation:
Path1: 0→1→ 2 (risk value: 2)
The minimum risk value is 2.

Give n =3, m =4, x =[0, 0, 1, 2], y =[1, 2, 3, 3], w =[1, 2, 3, 4], return3.

Explanation:
Path1: 0→1→ 3 (risk value: 3)
Path2: 0→2→ 3 (risk value: 4)
The minimum risk value is 3.

Give n =4, m =5, x =[0, 1, 1, 2, 3], y =[1, 2, 3, 4, 4], w =[3, 2, 4, 2, 1], return3.

Explanation:
Path1: 0→1→ 2 → 4 (risk value: 3)
Path2: 0→1→ 3 → 4 (risk value: 4)
The minimum risk value is 3.

Give n =5, m =7, x =[0, 0, 1, 2, 3, 3, 4], y =[1, 2, 3, 4, 4, 5, 5], w =[2, 5, 3, 4, 3, 4, 1], return3.

Explanation:
Path1: 0→1→ 3 → 5 (risk value: 4)
Path2: 0→1→ 3 → 4 → 5 (risk value: 3)
Path3: 0→2→ 4 → 3 → 5 (risk value: 5)
Path4: 0→2→ 4 → 5 (risk value: 5)
The minimum risk value is 3.

1. 用剪枝的dfs，如果当前路径的最大风险值已经超出了整体路径的最小值，则此路径不会成为答案. 应当注意此题为无向图，所以从x到y和从y到x都需要被记录
2. 用 best first search, 用pq， 复杂度很高

3. Kuraskal （寻找minimum tree path, 就是连接所有点，并且权重和最小的路径）可以用并查集实现，将图中所有点罗列，然后按权重排序（mlogm), 逐个点加入到集合中直到0和n在同一集合中终止，因为排好了序，所以此时边的权重为答案（因为答案是寻找从0到n的所有路径中的最小权重（每一路径中的最大权重为其权重））

4. pruning dfs

class Node {
    int to;
    int weight;
    public Node (int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}
public class Solution {
    /**
     * @param n: maximum index of position.
     * @param m: the number of undirected edges.
     * @param x: 
     * @param y: 
     * @param w: 
     * @return: return the minimum risk value.
     */
    public int dfs(int curIndex, int tarIndex, ArrayList[] map, int[] isVisited,int pathAns, int globalAns) {
        if (curIndex == tarIndex) {
            return pathAns;
        }

        if (pathAns >= globalAns) {
            return Integer.MAX_VALUE;
        }

        isVisited[curIndex] = 1;
        for (int i = 0; i < map[curIndex].size(); i++) {
            Node node = (Node) map[curIndex].get(i);
            if (isVisited[node.to] == 1) {
                continue;
            }
            globalAns = Math.min(globalAns, dfs(node.to, tarIndex, map, isVisited, Math.max(pathAns, node.weight), globalAns));
        }
        isVisited[curIndex] = 0;
        return globalAns;
    }

    public int getMinRiskValue(int n, int m, int[] x, int[] y, int[] w) {
        // Write your code here
        ArrayList[] map = new ArrayList[n + 1];
        for (int i = 0; i < m; i++) {
            if (map[x[i]] == null) {
                map[x[i]] = new ArrayList<>();
            }
            if (map[y[i]] == null) {
                map[y[i]] = new ArrayList<>();
            }
            map[x[i]].add(new Node(y[i], w[i]));
            map[y[i]].add(new Node(x[i], w[i]));
        }

        int[] isVisited = new int[n + 1];

        return dfs(0, n, map, isVisited, 0, Integer.MAX_VALUE);
    }
}

3.

class UF {
    int[] father;
    public UF(int n) {
        father = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    public int find(int a) {
        if (father[a] == a) {
            return a;
        }
        return father[a] = find(father[a]);
    }

    public boolean connected(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        return root_a == root_b;
    }

    public void union(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);

        father[root_a] = root_b;
    }
}

class Edge {
    int x;
    int y;
    int weight;
    public Edge(int x, int y, int weight) {
        this.x = x;
        this.y = y;
        this.weight = weight;
    }
}
public class Solution {
    /**
     * @param n: maximum index of position.
     * @param m: the number of undirected edges.
     * @param x: 
     * @param y: 
     * @param w: 
     * @return: return the minimum risk value.
     */
    public int getMinRiskValue(int n, int m, int[] x, int[] y, int[] w) {
        // Write your code here

        Edge[] edges = new Edge[m];
        for (int i = 0; i < x.length; i++) {
            edges[i] = new Edge(x[i], y[i], w[i]);
        }

        Arrays.sort(edges, new Comparator<Edge>(){
            public int compare(Edge a, Edge b) {
                return a.weight - b.weight;
            }
        });
        UF uf = new UF(n);
        for (Edge edge : edges) {
            if (!uf.connected(edge.x, edge.y)) {
                uf.union(edge.x, edge.y);
            }

            if (uf.connected(0, n)) {
                return edge.weight;
            }
        }
        return -1;
    }
}