Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-24SRM364 (Practice)

SRM 364 PowerPlants

|  SRM 364 PowerPlants - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 364 PowerPlants - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8062

  • 2^16の状態を持ちながらダイクストラするだけ。
  • numPlants以上のplantsが生きてればいい(丁度でなくてもいい)ので注意
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PowerPlants {

	int INF = 10000000;
	
	class State {
		int stat;
		int cost;
		State(int s, int c) {
			stat = s;
			cost = c;
		}
	}
	
	public int minCost(String[] connectionCost, String plantList, int numPlants) {
		int len = connectionCost.length;
		int[][] graph = new int[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				char c = connectionCost[i].charAt(j);
				if ('0' <= c && c <= '9') {
					graph[i][j] = c - '0';
				} else {
					graph[i][j] = 10 + c - 'A';
				}
			}
 		}
		
		int[] dp = new int[1<<len];
		Arrays.fill(dp, INF);
		
		
		int initptn = 0;
		for (int i = 0 ; i < len ; i++) {
			if (plantList.charAt(i) == 'Y') {
				initptn |= (1<<i);
			}
		}
		dp[initptn] = 0;
		
		Queue<State> q = new PriorityQueue<State>(4000000, new Comparator<State>(){
			public int compare(State arg0, State arg1) {
				return arg0.cost - arg1.cost;
			}
		});
		q.add(new State(initptn, 0));
		
		while (q.size() >= 1) {
			State s = q.poll();
			for (int i = 0 ; i < len ; i++) {
				if ((s.stat & (1<<i)) == 0) {
					int mcost = 10000;
					int mwake = -1;
					for (int j = 0 ; j < len ; j++) {
						if ((s.stat & (1<<j)) >= 1) {
							if (mcost > graph[j][i]) {
								mcost = graph[j][i];
								mwake = j;
							}
						}
					}
					if (mwake >= 0) {
						int tc = mcost + s.cost;
						int ts = s.stat | (1<<i);
						if (dp[ts] > tc) {
							dp[ts] = tc;
							q.add(new State(ts, tc));
						}
					}
				}
			}
		}
		
		int mcost = INF;
		for (int i = 0 ; i < (1<<len) ; i++) {
			if (Integer.bitCount(i) >= numPlants) {
				mcost = Math.min(mcost, dp[i]);
			}
		}
		return mcost;
	}
}