Poj Solution 2502

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

//* @author:
import java.util.Scanner;
import java.io.*;

public class Main{
 double max = Double.MAX_VALUE;
 int fin[] = new int[205];
 double d[] = new double[205];
 double dis[][] = new double[205][205];
 pos p[] = new pos[205];

 void initial() {
  for (int i = 0; i < 205; i++)
    p[i] = new pos();
  Scanner s;
  int n = 2;
  try {
    s = new Scanner(System.in);
    p[0].x = s.nextInt();
    p[0].y = s.nextInt();
    p[1].x = s.nextInt();
    p[1].y = s.nextInt();

    int flag = 0;
    while (s.hasNext()) {
    p[n].x = s.nextInt();
    p[n].y = s.nextInt();
    if (p[n].x == -1 && p[n].y == -1) {
         flag = 0;
      continue;
    }
    if (flag == 1) {
      dis[n][n - 1] = dis[n - 1][n] = Math
       .sqrt((p[n].x - p[n - 1].x) * (p[n].x - p[n - 1].x)
       + (p[n].y - p[n - 1].y)
       * (p[n].y - p[n - 1].y)) / 40000;
    }
    n++;
    flag = 1;
     }
   } catch (Exception e1) {
   }

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
         if (i != j && dis[i][j] == 0)
        dis[i][j] = dis[j][i] = (Math.sqrt((p[j].x - p[i].x)
        * (p[j].x - p[i].x) + (p[j].y - p[i].y)
        * (p[j].y - p[i].y))) / 10000.0;

  fin[0] = 1;
  for (int i = 0; i < n; i++)
    d[i] = dis[0][i];
  int v = 0;
  for (int i = 1; i < n; i++) {
    double min = max;
       for (int j = 0; j < n; j++)
          if (fin[j] != 1)
            if (d[j] < min) {
           v = j;
           min = d[j];
         }
        fin[v] = 1;
        for (int w = 0; w < n; w++)
          if (fin[w] != 1 && (min + dis[v][w] < d[w]))
            d[w] = min + dis[v][w];

    }
    double ans = 60.0 * d[1];
    System.out.println(Math.round(ans));
 }

  public static void main(String[] args) {
    Main di = new Main ();
    di.initial();
  }
}

class pos {
    int x = 0;
    int y = 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *