```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 ``` ```import java.util.*; // A0087884H // Lim Jiew Meng class Supermarket { private int N; // number of items in the supermarket. V = N+1 private int K; // the number of items that Steven has to buy private int[] shoppingList; // indices of items that Steven has to buy private int[][] T; // the complete weighted graph that measures the direct walking time to go from one point to another point in seconds private HashMap> memo; // memo of TSP(source, visited) private HashMap> sssp; // sssp of any 2 required nodes and source public Supermarket() { } int Query() { memo = new HashMap>(); sssp = new HashMap>(); // preprocess: compute sssp between any 2 nodes/source int node1, node2; for (int i = 0; i < K+1; i++) { HashMap tmp = new HashMap(); node1 = i; if (node1 != 0) { node1 = shoppingList[i-1]; } for (int j = 0; j < K+1; j++) { // find shortest part between any 2 shopping list items (i-1 | j-1) and source (0) node2 = j; if (node2 != 0) { node2 = shoppingList[j-1]; } if (node1 != node2) { tmp.put(node2, dijkstra(node1, node2)); } else { tmp.put(node2, 0); } System.out.println("SP from " + node1 + " to " + node2 + " is " + tmp.get(node2)); } // 2D HashMap for shortest path between any 2 shopping item and source. eg. // | 0 1 4 7 // --+------------- // 0 | // 1 | // 4 | // 7 | sssp.put(node1, tmp); } // actual query return TSP(0, 0); } int TSP(int source, int visited) { //System.out.println("source/visited = " + source + " / " + visited); //System.out.println(visited + " =? " + ((int)(Math.pow(2, K)-1))); if (visited == (int)(Math.pow(2, K)-1)) { // all required visited System.out.println("TSP (all) " + source + ", visited: " + visitedString(visited) + " = " + sssp.get(source).get(0)); return sssp.get(source).get(0); // return to source (0) } else if (memo.containsKey(source) && memo.get(source).containsKey(visited)) { System.out.println("TSP (DP) " + source + ", visited: " + visitedString(visited) + " = " + memo.get(source).get(visited)); return memo.get(source).get(visited); } else { int item; if (!memo.containsKey(source)) { memo.put(source, new HashMap()); } memo.get(source).put(visited, 1000000); for (int v = 0; v < K; v++) { item = shoppingList[v]; if (!hasVisited(visited, item)) { //System.out.println("trying to mark " + v + " as visited"); memo.get(source).put(visited, Math.min( memo.get(source).get(visited), sssp.get(source).get(item) + TSP(item, visit(visited, v)) )); //System.out.println("Considering: " + source + " to " + visited + "=" + memo[source][visited] + " vs " + SPBetItems.get(source).get(item) + TSP(item, visit(visited, item))); } } System.out.println("TSP " + source + ", visited: " + visitedString(visited) + " = " + memo.get(source).get(visited)); return memo.get(source).get(visited); } } int dijkstra(int src, int dest) { //System.out.println("====== DIJKSTRA from " + src + " to " + dest); PriorityQueue PQ = new PriorityQueue(); HashMap dist = new HashMap(); // shortest known dist from {src} to {node} // init shortest known distance for (int i = 0; i < N+1; i++) { if (i != src) { dist.put(i, Integer.MAX_VALUE); // dist to any {i} is big(unknown) by default } else { dist.put(src, 0); // dist to {src} is always 0 } } IntegerPair node; int nodeDist; int nodeIndex; PQ.offer(new IntegerPair(0, src)); while (PQ.size() > 0) { node = PQ.poll(); nodeDist = node.first(); nodeIndex = node.second(); if (nodeDist == dist.get(nodeIndex)) { // process out going edges //System.out.println("DIJKSTRA polled: { " + nodeDist + ", " + nodeIndex + " }"); for (int v = 0; v < N+1; v++) { // since its a complete graph, process all edges if (v != nodeIndex) { // except curr node if (dist.get(v) > dist.get(nodeIndex) + T[nodeIndex][v]) { // relax if possible dist.put(v, dist.get(nodeIndex) + T[nodeIndex][v]); PQ.offer(new IntegerPair(dist.get(v), v)); //System.out.println("DIJKSTRA new: { " + v + ", " + dist.get(v) + " }"); } } } } } return dist.get(dest); } int visit(int visited, int node) { //System.out.println(">> marking " + node + " becomes " + Integer.toBinaryString(visited | (1 << node))); return visited | (1 << node); } boolean hasVisited(int visited, int node) { return (visited & (1 << node)) == (1 << node); } String visitedString(int visited) { String visitedStr = ""; String binaryString = Integer.toBinaryString(visited); //System.out.println("binary visited: \""+ visited + "=" + binaryString + "\""); char[] chars = binaryString.toCharArray(); for (int i = 0; i < chars.length; i++) { if (chars[i] == '1') { visitedStr += shoppingList[i] + " "; } } return visitedStr; } void run() { // do not alter this method Scanner sc = new Scanner(System.in); int TC = sc.nextInt(); // there will be several test cases while (TC-- > 0) { // read the information of the complete graph with N+1 vertices N = sc.nextInt(); K = sc.nextInt(); // K is the number of items to be bought shoppingList = new int[K]; for (int i = 0; i < K; i++) shoppingList[i] = sc.nextInt(); T = new int[N+1][N+1]; for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) T[i][j] = sc.nextInt(); System.out.println(Query()); } } public static void main(String[] args) { // do not alter this method Supermarket ps7 = new Supermarket(); ps7.run(); } } class IntegerPair implements Comparable { Integer _first, _second; public IntegerPair(Integer f, Integer s) { _first = f; _second = s; } public int compareTo(Object o) { if (this.first() != ((IntegerPair)o).first()) return this.first() - ((IntegerPair)o).first(); else return this.second() - ((IntegerPair)o).second(); } Integer first() { return _first; } Integer second() { return _second; } } ```