TopCoder SRM 667 Div1 Easy: OrderOfOperations

解法

各bitを頂点，各bit間の遷移を辺としてダイクストラする．

コード

import java.util.Arrays;
import java.util.PriorityQueue;

public class OrderOfOperations {

	public int minTime(String[] s) {

		int N = s.length;
		int M = s[0].length();

		int[] operations = new int[N];
		for (int i = 0; i < N; i++) {
			operations[i] = Integer.parseInt(s[i], 2);
		}

		int[] cost = new int[1 << M];
		Arrays.fill(cost, Integer.MAX_VALUE / 100);
		cost[0] = 0;
		PriorityQueue<Edge> queue = new PriorityQueue<>();
		queue.add(new Edge(0, 0));
		while (!queue.isEmpty()) {
			Edge edge = queue.poll();

			for (int i = 0; i < N; i++) {
				int next = operations[i] | edge.bit;
				int k = Integer.bitCount(next ^ edge.bit);
				int c = k * k;
				if (cost[next] > cost[edge.bit] + c) {
					cost[next] = cost[edge.bit] + c;
					queue.add(new Edge(next, cost[next]));
				}
			}
		}

		int goal = 0;
		for (int i = 0; i < N; i++) {
			goal = goal | operations[i];
		}
		return cost[goal];
	}
}

class Edge implements Comparable<Edge> {
	int bit, cost;

	public Edge(int bit, int cost) {
		this.bit = bit;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}