KiloManX - TopCoder Dijkstra (Heap method)I just adapted the wonderful solution from the link below to Javahttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3Problem statement:http://community.topcoder.com/stat?c=problem_statement&pm=2288&rd=4725&rm=&cr=277659This problem was used for: Single Round Match 181 Round 1 - Division I, Level ThreeI found the solution interesting, because it uses bit representation in an int variable, so it knows which bosses he already killed, and hence he has the weapons from that boss.It's a very efficient solution.Syntax highlighted used http://tohtml.com/java/import java.util.TreeSet;public class KiloManX { class node implements Comparable<node> { int weapons; int shots; public node(int weapons, int shots) { this.weapons = weapons; this.shots = shots; } @Override public int compareTo(node o) { if (shots < o.shots) { return -1; } if (shots > o.shots) { return 1; } return 1; } } int leastShots(String[] damageChart, int[] bossHealth) { int numWeapons = bossHealth.length; boolean[] visited = new boolean[32768]; TreeSet<node> pq = new TreeSet<>(); pq.add(new node(0, 0)); while (pq.isEmpty() == false) { node top = pq.pollFirst(); // Make sure we don't visit the same configuration twice if (visited[top.weapons]) { continue; } visited[top.weapons] = true; // A quick trick to check if we have all the weapons, meaning we defeated all the bosses. // We use the fact that (2^numWeapons - 1) will have all the numWeapons bits set to 1. if (top.weapons == (1 << numWeapons) - 1) { return top.shots; } for (int i = 0; i < damageChart.length; i++) { // Check if we've already visited this boss, then don't bother trying him again if (((top.weapons >> i) & 1) != 0) { continue; } // Now figure out what the best amount of time that we can destroy this boss is, given the weapons we have. // We initialize this value to the boss's health, as that is our default (with our KiloBuster). int best = bossHealth[i]; for (int j = 0; j < damageChart.length; j++) { if (i == j) { continue; } if ((((top.weapons >> j) & 1) != 0) && damageChart[j].charAt(i) != '0') { // We have this weapon, so try using it to defeat this boss int shotsNeeded = bossHealth[i] / (damageChart[j].charAt(i) - '0'); if (bossHealth[i] % (damageChart[j].charAt(i) - '0') != 0) { shotsNeeded++; } best = (best < shotsNeeded) ? best : shotsNeeded; } } // Add the new node to be searched, showing that we defeated boss i, and we used 'best' shots to defeat him. pq.add(new node(top.weapons | (1 << i), top.shots + best)); } } return -1; } /** * @param args the command line arguments */ public static void main(String[] args) { KiloManX app = new KiloManX(); System.out.println(app.leastShots( new String[]{"070", "500", "140"}, new int[]{150, 150, 150})); System.out.println(app.leastShots( new String[]{"1542", "7935", "1139", "8882"}, new int[]{150, 150, 150, 150})); System.out.println(app.leastShots( new String[]{"07", "40"}, new int[]{150, 10})); System.out.println(app.leastShots( new String[]{"198573618294842", "159819849819205", "698849290010992", "000000000000000", "139581938009384", "158919111891911", "182731827381787", "135788359198718", "187587819218927", "185783759199192", "857819038188122", "897387187472737", "159938981818247", "128974182773177", "135885818282838"}, new int[]{157, 1984, 577, 3001, 2003, 2984, 5988, 190003, 9000, 102930, 5938, 1000000, 1000000, 5892, 38})); System.out.println(app.leastShots( new String[]{"02111111", "10711111", "11071111", "11104111", "41110111", "11111031", "11111107", "11111210"}, new int[]{28, 28, 28, 28, 28, 28, 28, 28})); }} #outer-wrapper { margin: 0px; margin-left: