1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * ACM Training 2009
 * ACM Problem #216 - Getting in Line
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=48&problem=152&mosmsg=Submission+received+with+ID+7356798
 *
 * @author Felix Dietrich
 * @version 1.0, 08/31/2009
 *
 * Methode: Backtracking
 * Status : Accepted
 * Runtime: 0.560
 */

public class Main
{
    public static class Computer
    {

        public int y;
        public int x;

        public Computer(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

    }

    public static void main(String... str) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new FileReader("testfile.txt"));
        
        Map<Integer,List<List<Integer>>> permutations = new HashMap<Integer, List<List<Integer>>>();
        
        for(int i=2; i<=8; i++)
        {
            solutions =  new ArrayList<List<Integer>>();
            track(new ArrayList<Integer>(), 0, i);
            permutations.put(i, solutions);
            
            //System.out.println(i + "! = " + solutions.size());
        }
        
        String input;
        StringTokenizer st;
        List<Computer> compList = new ArrayList<Computer>();
        Map<Integer, List<Integer>> sums = new HashMap<Integer, List<Integer>>();
        
        while((input=br.readLine()) != null)
        {
            int computers = Integer.parseInt(input);
            
            if(computers == 0)
                return;
            
            // read in the computer data
            compList.clear();
            sums.clear();
            for(int c=0; c<computers; c++)
            {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                compList.add(new Computer(x,y));
            }
            
            // get the precalculated solutions for this amount of computers
            solutions = permutations.get(computers);
            
            // calculate the sums of all solutions
            for(List<Integer> sol: solutions)
            {
                sums.put(getLen(sol, compList), sol);
            }
            
            int min = Collections.min(sums.keySet());
            printSolution(compList, sums.get(min), min);
        }
    }

    private static int testCase = 1;
    /**
     * Prints the given solution
     * @param list
     * @param min
     */
    private static void printSolution(List<Computer> compList, List<Integer> computerPermutation, int min)
    {
        System.out.println("**********************************************************");
        System.out.println("Network #" + testCase);
        
        int lastI = computerPermutation.get(0);
        Computer c1;
        Computer c2;
        for(int i=1; i<computerPermutation.size(); i++)
        {
            c1 = compList.get(lastI);
            lastI = computerPermutation.get(i);
            c2 = compList.get(lastI);
            System.out.println(String.format("Cable requirement to connect (%d,%d) to (%d,%d) is %.02f feet.", c1.x,c1.y,c2.x,c2.y,getDist(c1,c2)+16));
        }
        
        System.out.println(String.format("Number of feet of cable required is %.02f.",(double)min/100.));
        
        testCase++;
    }

    /**
     * Returns the cable length of the given network solution.
     * @param sol
     * @param compList
     * @return cable length
     */
    private static int getLen(List<Integer> sol, List<Computer> compList)
    {
        double sum = 0;
        int lastIndex = sol.get(0);
        Computer c1;
        Computer c2;
        for(int solNumber=1; solNumber<sol.size(); solNumber++)
        {
            c1 = compList.get(lastIndex);
            lastIndex = sol.get(solNumber);
            c2 = compList.get(lastIndex);
                
            sum += getDist(c1, c2) + 16;
        }
        return (int)Math.round(sum*100.);
    }

    /**
     * Returns the distance between two computers.
     * @param computer1
     * @param computer2
     * @return distance
     */
    private static double getDist(Computer computer1, Computer computer2)
    {
        int dx = computer1.x-computer2.x;
        int dy = computer1.y-computer2.y;
        return Math.sqrt(dx*dx + dy*dy);
    }
    
    ///////////////////////////////////////////////////////////////////
    //// Backtracking part.

    private static List<List<Integer>> solutions;
    private static void track(List<Integer> mySolution, int row, int max)
    {
        if(row >= max)
        {
            solutions.add(mySolution);
            return;
        }
            
        for(int col=0; col<max; col++)
        {
            if(possibleSolution(mySolution, row, col))
            {
                List<Integer> s = new ArrayList<Integer>(mySolution);
                s.add(col);
                track(s, row + 1, max);
            }
        }
    }
    
    // possible solution function for simple permutation
    private static boolean possibleSolution(List<Integer> mySolution, int row, int col)
    {
        if(mySolution.contains(col))
            return false;
        return true;
    }
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* 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 Kratzer Kevin
* @version 1.0, 11/04/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.312
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Formatter;
import java.util.Locale;
import java.util.Scanner;
public class Main216 {
protected final BufferedReader input;
protected final BufferedWriter out;
private double bestSolution = Double.MAX_VALUE;
public Main216() {
input = new BufferedReader(new InputStreamReader(System.in));
out = new BufferedWriter(new OutputStreamWriter(System.out));
}

void process() throws IOException {
Scanner s = new Scanner(input);
Formatter formatter = new Formatter(out, Locale.US);
int number = 0;
for(int amount = s.nextInt(); amount != 0; amount = s.nextInt()) {
number++;
out.append("**********************************************************\nNetwork #");
out.append(String.valueOf(number));
out.newLine();
double[][] matrix = new double[amount][amount];
int[][] input = new int[amount][2];
for(int i = 0; i < amount; i++) {
input[i][0] = s.nextInt();
input[i][1] = s.nextInt();
}
for(int i = 0; i < amount; i++) {
for(int j = 0; j < amount; j++) {
matrix[i][j] = calcDistance(input[i],input[j])+16;
}
}
BestSolution solution = new BestSolution();
for(int i = 0; i < amount; i++) {
int[] route = new int[amount];
route[0] = i;
backtrack(matrix,route,1,0, solution);
}
int[] route = solution.getRoute();

for(int i = 0; i < amount-1; i++) {
formatter.format("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",input[route[i]][0],input[route[i]][1],input[route[i+1]][0],input[route[i+1]][1],matrix[route[i]][route[i+1]]);

}
formatter.format("Number of feet of cable required is %.2f.\n",solution.getDistance());
formatter.flush();
}
out.flush();
}

private void backtrack(double[][] matrix, int[] route, int connectedPoints, double costsUntilNow, BestSolution solution) {
int amount = route.length;
for(int i = 0; i < amount; i++) {
int[] newRoute = new int[amount];
System.arraycopy(route,0,newRoute,0,amount);
boolean valid = true;
for(int j = 0; j < connectedPoints && valid; j++) {
if(route[j] == i) {
valid = false;
}
}
int pointsConnected = connectedPoints;
double costs = costsUntilNow;
if(valid) {
newRoute[pointsConnected] = i;
costs += matrix[newRoute[pointsConnected-1]][i];
pointsConnected = pointsConnected+1;
if(pointsConnected == amount) {
solution.setSolution(newRoute, costs);
} else if(solution.isBetter(costs)) {
backtrack(matrix,newRoute,pointsConnected,costs, solution);
}
}
}
}


private double calcDistance(int[] one, int[] two) {
return Math.sqrt(((one[0]-two[0])*(one[0]-two[0])) + ((one[1]-two[1])*(one[1]-two[1])));
}


public static void main(String... args) throws Exception {
new Main216().process();
}

private class BestSolution {
private double distance = Double.MAX_VALUE;
private int[] route = null;
public double getDistance() {
return distance;
}
public int[] getRoute() {
return route;
}
public void setSolution(int[] route, double distance) {
if(isBetter(distance)) {
this.route = route;
this.distance = distance;
}
}
public boolean isBetter(double distance) {
return this.distance > distance;
}


}

}