TopCoder SRM 551 Div1 Medium: ColorfulWolves

問題

TopCoder Statistics - Problem Statement

解法

100問マラソンはプライドを捨てて AC/Open が高い簡単な問題から解いていくことにした。

from->to の移動が可能な時、実際に移動するためには i < to となる from->i の経路を全て潰すことになるので、そのコストを辺 from->to のコストと見れば、 0->N-1 のダイクストラをすれば良い。

コード

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

public class ColorfulWolves {
	private final int INF = 100000;
	public int getmin(String[] colormap) {
		int N = colormap.length;

		ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<Edge>());
		}
		for (int from = 0; from < N; from++) {
			int cost = 0;
			for (int to = 0; to < N; to++) {
				if (colormap[from].charAt(to) != 'Y') {
					continue;
				}
				graph.get(from).add(new Edge(to, cost));
				cost++;
			}
		}

		int[] dijkstra = new int[N];
		Arrays.fill(dijkstra, INF);
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
		priorityQueue.add(new Edge(0, 0));
		dijkstra[0] = 0;

		while (!priorityQueue.isEmpty()) {
			Edge e = priorityQueue.poll();
			int from = e.to;
			for (Edge edge : graph.get(from)) {
				if (dijkstra[edge.to] > dijkstra[from] + edge.cost) {
					dijkstra[edge.to] = dijkstra[from] + edge.cost;
					priorityQueue.add(new Edge(edge.to, dijkstra[edge.to]));
				}
			}
		}

		return dijkstra[N - 1] == INF ? -1 : dijkstra[N - 1];
	}
}
class Edge implements Comparable<Edge> {
	int to, cost;
	public Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}