じゅうりょうせいげん

に答える

重量制限と進行のある路線では、重量制限が最も小さい幹線を選択し、決定路線では重量制限が大きい幹線を選択しなければならない。

コード#コード#

import java.io.*;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static PriorityQueue<Edge> priorityQueue;
    static int[] p;
    static int[] rank;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        priorityQueue = new PriorityQueue<>();
        p = new int[n + 1];
        rank = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            p[i] = i;
            rank[i] = 1;
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            priorityQueue.add(new Edge(x, y, w));
            //bw.write(count + "\n");
        }
        String[] last = br.readLine().split(" ");
        int src = Integer.parseInt(last[0]);
        int dest = Integer.parseInt(last[1]);
        int ans = mst(src, dest);
        bw.write(ans + "\n");
        bw.close();
        br.close();
    }

    private static int mst(int src, int dest) {
        while (!priorityQueue.isEmpty()) {
            Edge e = priorityQueue.poll();
            int x = e.x;
            int y = e.y;
            union(x, y);
            if (find(src) == find(dest))
                return e.w;
        }
        return -1;
    }

    private static int union(int a, int b) {
        int ar = find(a);
        int br = find(b);

        if (ar != br) {
            if (rank[ar] < rank[br])
                p[ar] = br;
            else {
                p[br] = ar;
                if (rank[ar] == rank[br]) {
                    rank[ar]++;
                }
            }
        }
        return rank[ar];
    }

    private static int find(int a) {
        if (a == p[a])
            return a;
        else {
            int y = find(p[a]);
            p[a] = y;
            return y;
        }
    }
}

class Edge implements Comparable<Edge> {
    public int x;
    public int y;
    public int w;

    public Edge(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(o.w, this.w);
    }
}

追加