Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
JAVACODEimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Reader.init( System.in ); int N = Reader.nextInt(); Node[][] dp = new Node[N][40]; int s1 = 0; for (int i = 0; i < N; i++) { int cnt = Reader.nextInt(); if (i == 0) s1 = cnt; for (int j = 0; j < cnt; j++) { dp[i][j] = new Node(); dp[i][j].x = Reader.nextInt(); dp[i][j].y = Reader.nextInt(); if (i == 0) dp[i][j].l = 0; } } double ans = Integer.MAX_VALUE; //deal with 1st for (int c = 0; c < s1; c++) { //init for (int i = 2; i < N; i++) { for (int j = 0; j < 40 && dp[i][j] != null; j++) { dp[i][j].l = Integer.MAX_VALUE; } } //deal with 2nd for (int j = 0; j < 40 && dp[1][j] != null; j++) { double ll = (dp[0][c].x - dp[1][j].x) * (dp[0][c].x - dp[1][j].x) + (dp[0][c].y - dp[1][j].y) * (dp[0][c].y - dp[1][j].y); ll = Math.sqrt(ll); dp[1][j].l = ll; } //deal with 2nd to N for (int i = 2; i < N; i++) { for (int j = 0; j < 40 && dp[i][j] != null; j++) { for (int k = 0; k < 40 && dp[i - 1][k] != null; k++) { double ll = (dp[i][j].x - dp[i - 1][k].x) * (dp[i][j].x - dp[i - 1][k].x) + (dp[i][j].y - dp[i - 1][k].y) * (dp[i][j].y - dp[i - 1][k].y); ll = Math.sqrt(ll); dp[i][j].l = Math.min(dp[i][j].l, ll + dp[i - 1][k].l); } } } //deal with N and 1st for (int j = 0; j < 40 && dp[N - 1][j] != null; j++) { double ll = (dp[0][c].x - dp[N - 1][j].x) * (dp[0][c].x - dp[N -1][j].x) + (dp[0][c].y - dp[N - 1][j].y) * (dp[0][c].y - dp[N - 1][j].y); ll = Math.sqrt(ll); ans = Math.min(ans, dp[N - 1][j].l + ll); } } ans *= 100; System.out.println((int)ans); } } class Node{ int x, y; double l; } class Reader { static BufferedReader reader; static StringTokenizer tokenizer; /** call this method to initialize reader for InputStream */ static void init(InputStream input) { reader = new BufferedReader( new InputStreamReader(input) ); tokenizer = new StringTokenizer(""); } /** get next word */ static String next() throws IOException { while ( ! tokenizer.hasMoreTokens() ) { //TODO add check for eof if necessary tokenizer = new StringTokenizer( reader.readLine() ); } return tokenizer.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt( next() ); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator