1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.Vector;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 216 Getting in Line
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=152
*
* @author Weigl Joseph
* @author Müller Thomas
* @version 1.0, 05/02/2011
*
* Status : Accepted
* Runtime: 0.728
*/

class Node{

public int x;
public int y;

}

public class Main {

static double bestLength;
static int[] bestRoute;
static Node[] nodes;

public static double calcDist(Node a, Node b){
double dist = Math.sqrt(Math.abs(a.x-b.x)*Math.abs(a.x-b.x) + Math.abs(a.y-b.y)*Math.abs(a.y-b.y));
return dist;
}

public static void calcBestRoute(int[] route){
double length = 0;
for(int i = 0; i < route.length-1; i++){
length = length + calcDist(nodes[route[i]], nodes[route[i+1]]) + 16;
}
if(length <= bestLength){
bestLength = length;
bestRoute = route.clone();
}
}

public static void permutation(int n){
int[] x= new int[n];
Vector<Integer> y = new Vector<Integer>();
for(int j=0;j<n;j++){
y.addElement(j);
}
permute(n,x,y);
}
// es wird immer ein inthilfsarray übergeben mit einer Zahl gestrichen
// Also es wird immer eine Zahl aus y-> x verschoben
public static void permute(int n, int[] x,Vector<Integer> y){
for(int i=0; i<n; i++){
x[n-1]=y.elementAt(i);
// der comment dient hier nur dem bugtracking
// System.out.println(i + " Missisippi");
Vector<Integer> z= new Vector();
z=(Vector<Integer>) y.clone();
z.removeElementAt(i);
// so hier muss aus y der Wert rausgelöscht werden
permute(n-1,x,z);
if(n==1){
calcBestRoute(x);
// System.out.println(Arrays.toString(x));
}
}
}


public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token;

int n;
int network = 0;

while(reader.ready()){
network++;
token = new StringTokenizer(reader.readLine());
n = Integer.parseInt(token.nextToken());
if(n == 0)
break;
double dist;
System.out.println("**********************************************************");
System.out.println("Network #" + network);
nodes = new Node[n];
bestRoute = new int[n];
bestLength = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
token = new StringTokenizer(reader.readLine());
nodes[i] = new Node();
nodes[i].x = Integer.parseInt(token.nextToken());
nodes[i].y = Integer.parseInt(token.nextToken());
}
permutation(n);
for(int i = 0; i < bestRoute.length - 1; i++){
dist = calcDist(nodes[bestRoute[i]], nodes[bestRoute[i+1]])+16;
System.out.printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.%n", nodes[bestRoute[i]].x,nodes[bestRoute[i]].y,nodes[bestRoute[i+1]].x,nodes[bestRoute[i+1]].y, dist);
}
System.out.printf("Number of feet of cable required is %.2f.%n",bestLength);
}
}


..------------------------------------------------

}




1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 216 Getting in Line
* Link: http://uva.onlinejudge.org/external/2/216.pdf
*
* @author Viktoriya Ryabova
* @version 1.0, 03/23/2010
*
* Method : Backtracing
* Status : Accepted
* Runtime: 0.304
*/


import java.awt.Point;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
static Point [] pointsArray;
static boolean[] gespert;

static Point[] sortedArray;
static Point[] last;
static double shortest = Double.MAX_VALUE;
static double backt(int k, double dd){
if (shortest < dd)
return 0;

for (int i = 0; i < pointsArray.length; ++i){
if (!gespert[i]){
gespert[i] = true;
last[k] = pointsArray[i];
double temp=0;
if (k != 0)
temp= getDistance(last[k-1], last[k]);
if (k == pointsArray.length-1){
if (shortest > dd+temp){
shortest = dd+temp;
sortedArray = Arrays.copyOf(last,pointsArray.length);
gespert[i] = false;
return dd;
}
}
backt(k+1, dd+temp);
gespert[i] = false;
}
}
return 0;
}

public static void main(String[] args) {
DecimalFormat dF = new DecimalFormat("#0.00");

//System.out.println(getDistance(new Point(5,19), new Point(55,28)));
Scanner sc = new Scanner (System.in);
int counter = 1;
while (sc.hasNext()){
int count =sc.nextInt();
if( count==0) return;

pointsArray = new Point [count];
gespert = new boolean[count];
sortedArray = new Point[count];
last = new Point[count];
shortest = Double.MAX_VALUE;

for (int i = 0; i< count; i++){
int a = sc.nextInt();
int b = sc.nextInt();
Point point = new Point (a, b);

pointsArray [i] = point;
}
backt(0,0);
System.out.println("**********************************************************");
System.out.println("Network #"+counter);
for (int i = 0;i<count-1; ++i){
System.out.println("Cable requirement to connect ("+ sortedArray[i].x+","+sortedArray[i].y+") to ("+sortedArray[i+1].x+","+sortedArray[i+1].y+") is "+dF.format(getDistance(sortedArray[i], sortedArray[i+1])).replace(',', '.')+" feet.");
}
System.out.println("Number of feet of cable required is " +dF.format(shortest).replace(',', '.')+".");
++counter;



}
}
public static double getDistance ( Point a, Point b){

double distance = Math.sqrt(Math.pow((a.x-b.x), 2.0) + Math.pow((a.y-b.y), 2.0))+16;

return distance;

}

}