Code:

import java.util.HashMap;
import java.util.Iterator;
public class TownsvillePaths17 {
static final int A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9;
static int[] dists1 = {105, 175, 175, 135};
static int[] dists2 = {140, 120, 175, 135};
static int[] dists3 = {105, 175, 170, 110};
static int[] dists4 = {140, 145, 95, 165};
static int[] dists5 = {140, 120, 115, 165};
static int[] dists6 = {140, 145, 145, 110};
static int[] dists7 = {95, 130, 175, 135};
static int[] dists8 = {105, 160, 95, 165};
static int[] dists9 = {105, 160, 145, 110};
static int[] dists10 = {95, 130, 170, 110};
static int[] dists11 = {140, 145, 80, 135};
static int[] dists12 = {105, 85, 175, 135};
static int[] dists13 = {105, 160, 80, 135};
static int[] dists14 = {105, 85, 115, 165};
static int[] dists15 = {95, 110, 95, 165};
static int[] dists16 = {95, 110, 145, 110};
static int[] dists17 = {95, 110, 80, 135};
static int[][] dists = {dists1, dists2, dists3, dists4, dists5, dists6,
dists7, dists8, dists9, dists10, dists11, dists12, dists13,
dists14, dists15, dists16, dists17};
static int[] towns1 = {B, F, H};
static int[] towns2 = {A, D, H};
static int[] towns3 = {B, F, I};
static int[] towns4 = {A, E, G};
static int[] towns5 = {A, D, G};
static int[] towns6 = {A, E, I};
static int[] towns7 = {C, F, H};
static int[] towns8 = {B, E, G};
static int[] towns9 = {B, E, I};
static int[] towns10 = {C, F, I};
static int[] towns11 = {A, E, H};
static int[] towns12 = {B, D, H};
static int[] towns13 = {B, E, H};
static int[] towns14 = {B, D, G};
static int[] towns15 = {C, E, G};
static int[] towns16 = {C, E, I};
static int[] towns17 = {C, E, H};
static int[][] towns = {towns1, towns2, towns3, towns4, towns5, towns6,
towns7, towns8, towns9, towns10, towns11, towns12, towns13,
towns14, towns15, towns16, towns17};
static int[] mealCosts = {76, 94, 68, 75, 64, 64, 71, 80, 88}; // dollars
static int[] gasCosts = {168, 125, 150, 187, 134, 175, 141, 164, 160, 128}; // cents
static int minCost = Integer.MAX_VALUE;
static HashMap<String, Integer> candPaths = new HashMap<String, Integer>();
public static void init() {
for (int i = 0; i < mealCosts.length; i++)
mealCosts[i] *= 1000;
}
public static void main(String[] args) {
long time = System.currentTimeMillis();
init();
for (int i = 0; i < 17; i++)
backtrack(i, 0, 0, 400, 0, "");
Iterator<String> iter = candPaths.keySet().iterator();
System.out.println("The minimum cost is (unrounded) $" + minCost/1000.0);
while (iter.hasNext()) {
String currkey = iter.next();
if (candPaths.get(currkey) == minCost)
System.out.println(currkey + " is such a path.");
}
System.out.println("in " + (System.currentTimeMillis()-time)/1000.0 + " s");
}
// to keep everything in integers, spent is given in tenths of a cent!
// and gasleft is given in tenths of a litre
// elapsed means time elapsed since last meal
public static void backtrack(int pathnum, int ind, int spent, int gasleft, int elapsed,
String pathkey) {
if (gasleft < 0) return;
if (elapsed > 360) return;
if (ind == 4) {
int fillamount = 400 - gasleft;
spent += fillamount * gasCosts[J];
if (spent <= minCost) {
minCost = spent;
candPaths.put(pathkey.substring(0, pathkey.length()-2), spent);
}
return;
}
if (spent > minCost) return;
if (ind == 0) pathkey += Integer.toString(pathnum+1) + ": ";
int dist = dists[pathnum][ind];
// go on without stopping
backtrack(pathnum, ind+1, spent, gasleft-dist, elapsed+dist, pathkey +
Integer.toString(ind+1) + ", ");
if (ind > 0) {
int town = towns[pathnum][ind-1];
int fillamount = 400 - gasleft;
int gascost = fillamount * gasCosts[town];
int mealcost = mealCosts[town];
// stop just for gas
backtrack(pathnum, ind+1, spent+gascost, 400-dist, elapsed+dist, pathkey +
Integer.toString(ind+1) + "G, ");
// stop just to eat
backtrack(pathnum, ind+1, spent+mealcost, gasleft-dist, dist, pathkey +
Integer.toString(ind+1) + "F, ");
// stop to get gas and eat
backtrack(pathnum, ind+1, spent+mealcost+gascost, 400-dist, dist, pathkey +
Integer.toString(ind+1) + "GF, ");
}
}
}