TopCoder SRM 551 Div1 Medium: ColorfulWolves
解法
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; } }