Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.StringTokenizer;
- import java.lang.Math;
- import java.util.ArrayList;
- import java.util.PriorityQueue;
- public class primMain implements Runnable {
- StringTokenizer st;
- BufferedReader in;
- PrintWriter out;
- double ans;
- static int AAA=2000000000;
- //classes
- public static class Vertex implements Comparable<Vertex> {
- //double d;
- boolean visited;
- Vertex parent;
- long key;
- ArrayList<Edge> adj;
- public int compareTo(Vertex other) {
- Vertex ver = (Vertex) other;
- return (int) (key - ver.key);
- }
- public Vertex() {
- //d=0;
- adj = new ArrayList<Edge>();
- key=AAA;
- visited=false;
- }
- }
- public static class Edge {
- Vertex v1, v2;
- long weight;
- }
- /////////////
- //variables//
- /////////////
- int n;
- long x[];
- long y[];
- Vertex vertexes[];
- PriorityQueue<Vertex> que = new PriorityQueue<Vertex>();
- public static void main(String[] args) {
- new Thread(new primMain()).run();
- }
- public void run() {
- try {
- in = new BufferedReader(new FileReader("spantree.in"));
- out = new PrintWriter(new FileWriter("spantree.out"));
- solve();
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- out.flush();
- out.close();
- }
- }
- String nextToken() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine());
- }
- return st.nextToken();
- }
- int nextInt() throws NumberFormatException, IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws NumberFormatException, IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(nextToken());
- }
- void Prim (){
- vertexes[0].key=0;
- que.add(vertexes[0]);
- while (!que.isEmpty()) {
- Vertex u;
- u=new Vertex();
- u=que.remove();
- u.visited=true;
- int s=u.adj.size();
- Vertex v;
- v=new Vertex();
- Edge e;
- e=new Edge();
- Vertex vv;
- vv=new Vertex();
- for (int i=0; i<s;i++ ){
- e=u.adj.get(i);
- v=e.v2;
- if (/*(que.contains(v)) &&*/ (e.weight < v.key)&&(v.visited==false)) {
- v.parent=u;
- v.key=e.weight;
- vv=v;
- }
- }
- que.add(v);
- }
- }
- void solve() throws NumberFormatException, IOException {
- n = nextInt();
- x = new long[n];
- y = new long[n];
- vertexes = new Vertex[n];
- for (int i = 0; i < n; i++) {
- x[i] = nextLong();
- y[i] = nextLong();
- vertexes[i]=new Vertex();
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- long w =((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
- Edge e;
- e = new Edge();
- e.v1=vertexes[i];
- e.v2=vertexes[j];
- e.weight=w;
- vertexes[i].adj.add(e);
- }
- }
- Prim();
- for (int i=0;i<n; i++) {
- ans+=Math.sqrt(vertexes[i].key);
- }
- out.println(ans);
- }
- }
Add Comment
Please, Sign In to add comment