BOJ. Traveling Salesman problem (2098)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringBuilder sb = new StringBuilder();
	static int[][] dis;
	static int n;
	static int INF = 987654321;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		n = toi(br.readLine());
		int[] arr;
		dis = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {
			arr = getArr();
			for(int j = 1; j <= n; j++) dis[i][j] = arr[j - 1];
		}

		int[][] dp = new int[n + 1][1 << n];
		for(int[] ar: dp) Arrays.fill(ar, INF);

		print(dfs(dp, 1, 1));
	}

	static int dfs(int[][] dp, int idx, int bitmask) {
		if(dp[idx][bitmask] != INF) return dp[idx][bitmask];
		if(bitmask == (1 << n) - 1) {
			return dis[idx][1] == 0  ? INF : dis[idx][1];
		}

		int bit = 2; //b10
		int townIdx = 2;

		for(int i = 2; i <= n; i++) {
			if((bit & bitmask) == 0 && dis[idx][townIdx] != 0)
				dp[idx][bitmask] = Math.min(dp[idx][bitmask], dfs(dp, townIdx, bitmask | bit) + dis[idx][townIdx]);
			bit <<= 1;
			townIdx++;
		}
		return dp[idx][bitmask];
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static long tol(String s) { return Long.parseLong(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}