AOJ-2254: Fastest Route
解法
ビットDP。この手の、状態遷移でビットが立つだけ、みたいな問題は何も考えずに0から順に回してよい。集合をビットで表現したとき、包含関係が成り立つなら数値としての大小関係も満たされるから。
import java.util.Arrays; import java.util.Scanner; public class Main{ void run(){ Scanner in = new Scanner(System.in); for(;;){ int N = in.nextInt(); if(N==0) return ; int[] noEquip = new int[N]; int[][] matrix = new int[N][N]; for(int i=0; i<N; i++){ noEquip[i] = in.nextInt(); for(int j=0; j<N; j++){ matrix[i][j] = in.nextInt(); } } System.out.println(solve(noEquip, matrix)); } } int solve(int[] noEquip, int[][] matrix){ int N = noEquip.length; int[] dp = new int[1<<N]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for(int bit=0; bit<(1<<N); bit++){ for(int i=0; i<N; i++)if(((bit>>i)&1)==0){ int min = noEquip[i]; for(int j=0; j<N; j++)if(((bit>>j)&1)>0){ min = Math.min(min, matrix[i][j]); } dp[bit|(1<<i)] = Math.min(dp[bit|(1<<i)], dp[bit] + min); } } return dp[(1<<N)-1]; } public static void main(String[] args){ new Main().run(); } }