コード
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;
}
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;
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]);
}
}
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()) {
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];
}
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;
}
}
}