import java.io.*; import java.util.*; import java.math.*; /** * Solution to Super Mario 169 * * This problem is just a repeated application of a memoized Hamiltonian Path algorithm. * * We'll do some special things. In each case, we'll have a source and a list of points. * We'll go backwards, and find the shortest Hamiltonian Path from each point back to the source. * In most cases, Switches will be the source and Coins will be the points. * In the last case, Mario's Start is the source and the Switches are the points. * In each case, node 0 will be the source. * * @author vanb */ public class mario_vanb { public Scanner sc; public PrintStream ps; /** * A 3D point. * * @author vanb */ private class Point { /** Integer coordinates */ public int x, y, z; /** * Create a point. * * @param x X coord * @param y Y coord * @param z Z coord */ public Point( int x, int y, int z ) { this.x = x; this.y = y; this.z = z; } /** * Distance from this point to another point. * * @param p Another point * @return Distance from this point to P */ public double distance( Point p ) { double dx = p.x-x; double dy = p.y-y; double dz = p.z-z; return Math.sqrt( dx*dx + dy*dy + dz*dz ); } /** * A pretty String for debugging. * * @return A pretty String */ public String toString() { return "[" + x + "," + y + "," + z + "]"; } } /** Memoization array for Hamiltonian Path */ public double memo[][] = new double[14][1<<15]; /** Distances between points */ public double dists[][] = new double[15][15]; /** This is the state that the Hamiltonian Path code is trying to reach. */ public int target; /** This is the number of points in a Hamiltonian Path subproblem */ public int npoints; /** * This is the shortest path from this node to node 0, avoiding nodes already visited. * The state represents the nodes you've already visited, each state is a bit. * Node x is bit 1<