結果
問題 | No.126 2基のエレベータ |
ユーザー | ぴろず |
提出日時 | 2015-01-14 00:16:54 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 940 ms / 5,000 ms |
コード長 | 2,479 bytes |
コンパイル時間 | 2,637 ms |
コンパイル使用メモリ | 79,336 KB |
実行使用メモリ | 183,656 KB |
最終ジャッジ日時 | 2024-04-19 01:42:38 |
合計ジャッジ時間 | 32,445 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 916 ms
183,656 KB |
testcase_01 | AC | 905 ms
183,644 KB |
testcase_02 | AC | 912 ms
183,544 KB |
testcase_03 | AC | 892 ms
183,364 KB |
testcase_04 | AC | 910 ms
183,512 KB |
testcase_05 | AC | 914 ms
183,604 KB |
testcase_06 | AC | 890 ms
183,276 KB |
testcase_07 | AC | 902 ms
183,356 KB |
testcase_08 | AC | 906 ms
183,584 KB |
testcase_09 | AC | 902 ms
183,360 KB |
testcase_10 | AC | 930 ms
183,348 KB |
testcase_11 | AC | 940 ms
183,492 KB |
testcase_12 | AC | 935 ms
183,504 KB |
testcase_13 | AC | 936 ms
183,572 KB |
testcase_14 | AC | 929 ms
183,540 KB |
testcase_15 | AC | 913 ms
183,600 KB |
testcase_16 | AC | 925 ms
183,608 KB |
testcase_17 | AC | 913 ms
183,504 KB |
testcase_18 | AC | 915 ms
183,476 KB |
testcase_19 | AC | 909 ms
183,372 KB |
testcase_20 | AC | 909 ms
183,252 KB |
testcase_21 | AC | 906 ms
183,440 KB |
testcase_22 | AC | 915 ms
183,632 KB |
testcase_23 | AC | 917 ms
183,488 KB |
testcase_24 | AC | 914 ms
183,436 KB |
testcase_25 | AC | 913 ms
183,444 KB |
testcase_26 | AC | 902 ms
183,328 KB |
testcase_27 | AC | 915 ms
183,480 KB |
testcase_28 | AC | 895 ms
183,600 KB |
testcase_29 | AC | 914 ms
183,560 KB |
ソースコード
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); } } }