QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533066#8068. Building RoadstheodoregossettWA 55ms40084kbJava83.7kb2024-08-25 16:42:242024-08-25 16:42:24

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 16:42:24]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:40084kb
  • [2024-08-25 16:42:24]
  • 提交

answer

import java.util.*;

public class Main {

    static class Edge implements Comparable<Edge> {
        int vertex;
        double weight;

        public Edge(int vertex, double weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return Double.compare(this.weight, other.weight);
        }
    }

    // Method to compute the Euclidean distance between two points
    public static double getDistance(int x1, int y1, int x2, int y2) {
        return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }

    // Prim's algorithm to build MST from a given vertex
    public static List<List<Edge>> primMST(int n, int start, int[] xCoordinates, int[] yCoordinates) {
        boolean[] visited = new boolean[n];
        List<List<Edge>> mst = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            mst.add(new ArrayList<>());
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int vertex = current.vertex;

            if (visited[vertex]) continue;
            visited[vertex] = true;

            // For each unvisited adjacent vertex, add to the priority queue
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    double distance = getDistance(xCoordinates[vertex], yCoordinates[vertex], xCoordinates[i], yCoordinates[i]);
                    pq.add(new Edge(i, distance));
                    mst.get(vertex).add(new Edge(i, distance));
                    mst.get(i).add(new Edge(vertex, distance));
                }
            }
        }
        return mst;
    }

    // DFS to find the farthest node and its distance from the starting node
    public static double[] dfs(List<List<Edge>> mst, int current, boolean[] visited) {
        visited[current] = true;
        double maxDist = 0;
        double secondMaxDist = 0;

        for (Edge edge : mst.get(current)) {
            if (!visited[edge.vertex]) {
                double dist = edge.weight + dfs(mst, edge.vertex, visited)[0];
                if (dist > maxDist) {
                    secondMaxDist = maxDist;
                    maxDist = dist;
                } else if (dist > secondMaxDist) {
                    secondMaxDist = dist;
                }
            }
        }
        return new double[] { maxDist, maxDist + secondMaxDist };
    }

    // Method to find the diameter of the MST
    public static double getTreeDiameter(List<List<Edge>> mst, int start) {
        boolean[] visited = new boolean[mst.size()];
        double[] result = dfs(mst, start, visited);
        return result[1];  // The diameter of the tree is the max of the two longest paths
    }

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

        int[] xCoordinates = new int[n];
        int[] yCoordinates = new int[n];

        for (int i = 0; i < n; i++) {
            xCoordinates[i] = scanner.nextInt();
            yCoordinates[i] = scanner.nextInt();
        }

        double minDiameter = Double.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // Generate MST from each vertex
            List<List<Edge>> mst = primMST(n, i, xCoordinates, yCoordinates);
            // Find the diameter of the resulting tree
            double diameter = getTreeDiameter(mst, i);
            // Track the minimum diameter
            minDiameter = Math.min(minDiameter, diameter);
        }

        System.out.print(minDiameter);
        scanner.close();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 55ms
memory: 39300kb

input:

3
0 0
10 0
0 10

output:

20.0

result:

ok found '20.00000', expected '20.00000', error '0.00000'

Test #2:

score: -100
Wrong Answer
time: 51ms
memory: 40084kb

input:

9
0 0
10 0
0 10
-10 0
0 -10
10 10
10 -10
-10 10
-10 -10

output:

114.78708664619074

result:

wrong answer 1st numbers differ - expected: '28.28427', found: '114.78709', error = '3.05834'