結果
問題 | No.126 2基のエレベータ |
ユーザー |
![]() |
提出日時 | 2015-01-14 00:16:54 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 910 ms / 5,000 ms |
コード長 | 2,479 bytes |
コンパイル時間 | 2,608 ms |
コンパイル使用メモリ | 78,996 KB |
実行使用メモリ | 183,332 KB |
最終ジャッジ日時 | 2024-10-10 18:24:05 |
合計ジャッジ時間 | 31,315 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
package no126;import java.util.ArrayList;import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();System.out.println(solve(a,b,c));}public static int solve(int a,int b,int s) {Graph g = new Graph(101*101*101);for(int i=0;i<=100;i++) {for(int j=1;j<=100;j++) {for(int k=1;k<=100;k++) {int la = Math.abs(i-k);int lb = Math.abs(j-k);if (k == 1) {g.addEdge(map(i, j, k), map(0, 1, 0), la + 1);}else{if (la <= lb) {g.addEdge(map(i, j, k), map(0, j, 0), la + k);}else{g.addEdge(map(i, j, k), map(i, 1, 1), lb + (k-1));g.addEdge(map(i, j, k), map(i, i, i), lb + Math.abs(i-k));}}}}}int[] dist = g.minDistDijkstra(map(a,b,s));int ans = Graph.INF;for(int i=1;i<=100;i++) {ans = Math.min(ans,dist[map(0, i, 0)]);}return ans;}private static int map(int a,int b,int s) {return a + b * 101 + s * 101 * 101;}}class Graph {public static final int INF = 1<<29;int n;ArrayList<Edge>[] graph;@SuppressWarnings("unchecked")public Graph(int n) {this.n = n;this.graph = new ArrayList[n];for(int i=0;i<n;i++) {graph[i] = new ArrayList<Edge>();}}public void addBidirectionalEdge(int from,int to,int cost) {addEdge(from,to,cost);addEdge(to,from,cost);}public void addEdge(int from,int to,int cost) {graph[from].add(new Edge(to, cost));}//dijkstra O(ElogV)public int[] minDistDijkstra(int s) {int[] dist = new int[n];Arrays.fill(dist, INF);dist[s] = 0;PriorityQueue<Node> q = new PriorityQueue<Node>();q.offer(new Node(0, s));while(!q.isEmpty()) {Node node = q.poll();int v = node.id;if (dist[v] < node.dist) {continue;}for(Edge e:graph[v]) {if (dist[e.to] > dist[v] + e.cost) {dist[e.to] = dist[v] + e.cost;q.add(new Node(dist[e.to], e.to));}}}return dist;}class Edge {int to;int cost;public Edge(int to,int cost) {this.to = to;this.cost = cost;}}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) ? -1 : ((this.dist == o.dist) ? 0 : 1);}}}