TopCoder SRM 506 Div1 Medium: SlimeXGrandSlimeAuto

解法

mayokoex.hatenablog.com

街aから街bに移動する時、街cにある車を使うと、a->cを歩き、c->bを車で移動する。

コード

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

public class SlimeXGrandSlimeAuto {
	private final int INF = 1000000;

	public int travel(int[] cars, int[] districts, String[] roads,
			int invWalkSpeed, int invDriveSpeed) {
		int N = roads.length;

		// 距離の入力を受け取る
		int[][] dist = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				char c = roads[i].charAt(j);
				int d = INF;
				if ('0' <= c && c <= '9') {
					d = (int) (c - '0' + 1);
				} else if ('a' <= c && c <= 'z') {
					d = (int) (c - 'a' + 11);
				} else if ('A' <= c && c <= 'Z') {
					d = (int) (c - 'A' + 37);
				}
				dist[i][j] = d;
			}
			dist[i][i] = 0;
		}

		// ワーシャルフロイトで2点間の最小距離を出す
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}

		int distNum = districts.length;// 行く予定のリストの数
		int carNum = cars.length;// 車の数

		// cost[i][j]:= i番目の移動の時にj番目の車を使う場合のコスト
		int[][] cost = new int[distNum][carNum + 1];
		for (int i = 0; i < distNum; i++) {
			int from = 0;
			if (i > 0) {
				from = districts[i - 1];
			}
			int to = districts[i];

			// 車を使わない時
			cost[i][carNum] = invWalkSpeed * dist[from][to];

			// 車を使う時
			for (int j = 0; j < carNum; j++) {
				int walk = invWalkSpeed * dist[from][cars[j]];
				int drive = invDriveSpeed * dist[cars[j]][to];
				cost[i][j] = walk + drive;
			}
		}

		// 最小費用流で解く
		int start = distNum + carNum + 1;
		int goal = distNum + carNum + 2;
		PrimalDual graph = new PrimalDual(distNum + carNum + 3);
		for (int i = 0; i < distNum; i++) {
			graph.addEdge(start, i, 1, 0);
			for (int p = 0; p <= carNum; p++) {
				graph.addEdge(i, distNum + p, 1, cost[i][p]);
			}
		}

		// 車を使った場合からgoalへの流れ
		for (int i = 0; i < carNum; i++) {
			graph.addEdge(distNum + i, goal, 1, 0);
		}

		// 歩きは無制限に使える
		graph.addEdge(distNum + carNum, goal, INF, 0);

		return graph.minCostFlow(start, goal, distNum);
	}
}

class PrimalDual {
	final int INF = 1 << 29;
	int N;// 頂点数
	ArrayList<Edge>[] graph;

	@SuppressWarnings("unchecked")
	public PrimalDual(int N) {
		this.N = N;
		this.graph = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			graph[i] = new ArrayList<Edge>();
		}
	}

	public void addEdge(int from, int to, int cap, int cost) {
		graph[from].add(new Edge(to, cap, cost, graph[to].size()));
		graph[to].add(new Edge(from, 0, -cost, graph[from].size() - 1));
	}

	public int minCostFlow(int start, int goal, int flow) {
		int[] prevNode = new int[N];
		int[] prevEdge = new int[N];
		int[] potential = new int[N];// ポテンシャル（既にかかったコスト）
		int totalCost = 0;
		while (flow > 0) {
			int[] dist = new int[N];
			Arrays.fill(dist, INF);
			dist[start] = 0;

			PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
			priorityQueue.offer(new Node(0, start));
			while (!priorityQueue.isEmpty()) {
				// キューから1番距離の近いノードを取り出す
				Node node = priorityQueue.poll();
				int v = node.id;
				if (dist[v] < node.dist) {
					// 暫定の最短距離よりも遠かったらスルー
					continue;
				}

				for (int i = 0; i < graph[v].size(); i++) {
					Edge e = graph[v].get(i);

					if (e.cap > 0
							&& dist[e.to] > dist[v] + e.cost + potential[v]
									- potential[e.to]) {
						dist[e.to] = dist[v] + e.cost + potential[v]
								- potential[e.to];
						priorityQueue.add(new Node(dist[e.to], e.to));

						// 直前の経路を記憶しておく
						prevNode[e.to] = v;
						prevEdge[e.to] = i;
					}
				}
			}

			// そもそもゴールまで辿りつけない場合はどうしようもない
			if (dist[goal] == INF) {
				return -1;
			}

			// 今回かかったコストをメモしておく
			for (int v = 0; v < N; v++) {
				potential[v] += dist[v];
			}

			// startからgoalまで流せるだけ流す
			int minFlow = flow;
			for (int now = goal; now != start; now = prevNode[now]) {
				minFlow = Math.min(minFlow,
						graph[prevNode[now]].get(prevEdge[now]).cap);
			}
			flow -= minFlow;
			totalCost += minFlow * potential[goal];

			for (int now = goal; now != start; now = prevNode[now]) {
				Edge edge = graph[prevNode[now]].get(prevEdge[now]);
				edge.cap -= minFlow;
				graph[now].get(edge.rev).cap += minFlow;
			}
		}
		return totalCost;
	}

	class Node implements Comparable<Node> {
		int dist;
		int id;

		public Node(int dist, int i) {
			this.dist = dist;
			this.id = i;
		}

		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
	}

	class Edge {
		int to, cap, cost, rev;

		public Edge(int to, int cap, int cost, int rev) {
			this.to = to;
			this.cap = cap;
			this.cost = cost;
			this.rev = rev;
		}
	}
}