Supermarket.java

import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
// write your matric number here: U095916B
// write your name here: Ng Yang Yi, Desmond
// write list of collaborators here (reading someone's post in Facebook group/IVLE discussion forum and using the idea is counted as collaborating):

class BUSupermarket {
	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 final int INF = 100000000;
	private final int INF = 100000000;
	private final int BITS = Integer.numberOfTrailingZeros(0);
	private int[][] smaller_graph, shortest_dist, memo;
	private int bitmask;
	private int calls;
	private int ALL_VISITED;
	private PriorityQueue<IntegerPair> pq;

	public BUSupermarket() {}

	int TSP() {
		for (int i=0; i < K; i++) memo[1<<i][i] = smaller_graph[0][i+1];
		int bestCost = INF;
		if ( K > 1 ) {
			int halfK = (int) Math.ceil(K / 2.0);
			int bitLimit = ALL_VISITED - ((1<<(halfK-1))-1);
			for (int set=3; set <= bitLimit; set++) {
				int count = Integer.bitCount(set);
				if ( count > halfK + 1 ) continue;
				int istart = Integer.numberOfTrailingZeros(set);
				int iend   = BITS - Integer.numberOfLeadingZeros(set);
				int[] memoSet = memo[set];
				for (int i = istart; i < iend; i++) {
					int srcMask = 1 << i;
					if ( (set & srcMask) ==  0 ) continue;
					int[] subset = memo[set ^ srcMask];
					for (int j = istart; j < iend; j++) {
						if ( subset[j] == INF ) continue;
						memoSet[i] = Math.min(memoSet[i],smaller_graph[i+1][j+1] + subset[j]);
					}
				}
			}
			
			for (int set1 = (1<<halfK)-1; set1 < ALL_VISITED; set1++) {
				int count = Integer.bitCount(set1);
				if ( count < halfK ) {
					set1 += (1<<(halfK-count))-1;
					continue;
				} else if ( count != halfK ) continue;
				int[] costSet1 = memo[set1];
				int istart = Integer.numberOfTrailingZeros(set1);
				int iend   = BITS - Integer.numberOfLeadingZeros(set1);
				for (int i = istart; i < iend; i++) {
					if ( (set1 & (1<<i)) == 0 ) continue;
					int set2 = (ALL_VISITED ^ set1) | (1<<i);
					int[] costSet2 = memo[set2];
					bestCost = Math.min(bestCost,costSet1[i] + costSet2[i]);
				}
			}
		} else {
			for (int i = 0; i < K; i++) bestCost = Math.min(bestCost,smaller_graph[0][i+1] + memo[ALL_VISITED][i]);
		}
		return bestCost;
	}

	void Dijkstra(int src, int index) {
		pq = new PriorityQueue<IntegerPair>();
		pq.offer(new IntegerPair(src, 0));
		shortest_dist[index][src] = 0;

		while (!pq.isEmpty()) {
			IntegerPair start = pq.poll();

			if (shortest_dist[index][start.vertex] < start.weight) continue;

			int next = 0;
			for (int dist : T[start.vertex]) {	
				if (shortest_dist[index][next] > dist + shortest_dist[index][start.vertex]) {
					shortest_dist[index][next] = dist + shortest_dist[index][start.vertex];
					pq.offer(new IntegerPair(next, shortest_dist[index][next]));
				}
				++next;
			}
		}
	}

	int Query() {
		int answer = 0;
		shortest_dist = new int[K+1][N+1];
		for (int i = 0; i <= K; i++) Arrays.fill(shortest_dist[i], INF);
		for (int i = 0; i <= K; i++) Dijkstra(shoppingList[i], i);

		smaller_graph = new int[K+1][K+1];
		for (int i = 0; i < K; i++) {
			for (int j = i+1; j <= K; j++) {
				smaller_graph[i][j] = smaller_graph[j][i] = shortest_dist[i][shoppingList[j]];
			}
			smaller_graph[i][i] = 0;
		}

		memo = new int[1<<K][K];
		for (int i = 0; i < memo.length; i++) {
			Arrays.fill(memo[i], INF);
		}
		this.calls = 0;
		answer = TSP();
		//System.out.println(this.calls);
		return answer;
	}

	void run() throws Exception {
		// do not alter this method to standardize the I/O speed (this is already very fast)
		long start = System.currentTimeMillis();
		IntegerScanner sc = new IntegerScanner(System.in);
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		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+1];
			for (int i = 1; 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();
			ALL_VISITED = (1<<K)-1; 
			pw.println(Query());
		}
		long end = System.currentTimeMillis();
		pw.println((end - start) / 1000.0);
		pw.close();
	}

	public static void main(String[] args) throws Exception {
		// do not alter this method
		BUSupermarket ps7 = new BUSupermarket();
		ps7.run();
	}
}



class IntegerPair implements Comparable<IntegerPair> {
	Integer vertex, weight;

	public IntegerPair(Integer f, Integer s) {
		vertex = f;
		weight = s;
	}

	public int compareTo(IntegerPair o) {
		if (!this.first().equals(o.first()))
			return this.first() - o.first();
		else
			return this.second() - o.second();
	}

	Integer first() { return weight; }
	Integer second() { return vertex; }
}

class IntegerScanner { // coded by Ian Leow for PS4
	BufferedInputStream bis;
	IntegerScanner(InputStream is) {
		bis = new BufferedInputStream(is, 1000000);
	}

	public int nextInt() {    
		int result = 0;
		try {
			int cur = bis.read();
			if(cur == -1)
				return -1;

			while(cur < 48 || cur > 57) {
				cur = bis.read();
			}
			while(cur >= 48 && cur <= 57) {
				result = result * 10 + (cur - 48);
				cur = bis.read();
			}
			return result;
		}
		catch(IOException ioe) {
			return -1;
		}
	}
}