結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | kenkoooo |
提出日時 | 2015-03-07 03:05:20 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 101 ms / 5,000 ms |
コード長 | 3,289 bytes |
コンパイル時間 | 2,335 ms |
コンパイル使用メモリ | 78,444 KB |
実行使用メモリ | 52,984 KB |
最終ジャッジ日時 | 2023-09-06 20:44:25 |
合計ジャッジ時間 | 5,948 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
49,508 KB |
testcase_01 | AC | 38 ms
49,332 KB |
testcase_02 | AC | 38 ms
49,336 KB |
testcase_03 | AC | 37 ms
49,168 KB |
testcase_04 | AC | 74 ms
51,316 KB |
testcase_05 | AC | 87 ms
52,732 KB |
testcase_06 | AC | 92 ms
52,984 KB |
testcase_07 | AC | 61 ms
51,300 KB |
testcase_08 | AC | 71 ms
50,848 KB |
testcase_09 | AC | 64 ms
51,220 KB |
testcase_10 | AC | 77 ms
52,340 KB |
testcase_11 | AC | 67 ms
51,296 KB |
testcase_12 | AC | 68 ms
51,204 KB |
testcase_13 | AC | 68 ms
51,656 KB |
testcase_14 | AC | 63 ms
52,072 KB |
testcase_15 | AC | 76 ms
51,496 KB |
testcase_16 | AC | 69 ms
51,332 KB |
testcase_17 | AC | 61 ms
51,220 KB |
testcase_18 | AC | 65 ms
49,460 KB |
testcase_19 | AC | 72 ms
52,068 KB |
testcase_20 | AC | 62 ms
51,644 KB |
testcase_21 | AC | 63 ms
51,648 KB |
testcase_22 | AC | 63 ms
51,580 KB |
testcase_23 | AC | 64 ms
51,356 KB |
testcase_24 | AC | 71 ms
52,044 KB |
testcase_25 | AC | 63 ms
51,116 KB |
testcase_26 | AC | 63 ms
51,172 KB |
testcase_27 | AC | 45 ms
49,680 KB |
testcase_28 | AC | 101 ms
51,996 KB |
testcase_29 | AC | 44 ms
49,592 KB |
ソースコード
import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class Main { public static void main(String[] args) { int N = nextInt(); int M = nextInt(); int start = nextInt(); int goal = nextInt(); Graph graph = new Graph(N); for (int i = 0; i < M; i++) { int a = nextInt(); int b = nextInt(); int c = nextInt(); graph.addBidirectionalEdge(a, b, c); } int[] dist = graph.minDistDijkstra(goal); ArrayList<Integer> list = new ArrayList<>(); int now = start; list.add(now); while (true) { if (now == goal) { break; } int next = Integer.MAX_VALUE; for (Graph.Edge edge : graph.graph[now]) { // nowから出ている全ての辺を見る if (dist[now] == dist[edge.to] + edge.cost) { // goalからedge.toを通ってnowへ行く経路が最短経路だったとき next = Math.min(edge.to, next); } } list.add(next); now = next; } StringBuilder sb = new StringBuilder(); for (Integer integer : list) { sb.append(integer); if (integer != goal) { sb.append(" "); } } System.out.println(sb.toString()); } static int nextInt() { int c; try { c = System.in.read(); while (c != '-' && (c < '0' || c > '9')) c = System.in.read(); if (c == '-') return -nextInt(); int res = 0; while (c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = System.in.read(); } return res; } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return -1; } } 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 start) { 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 (Edge e : graph[v]) { /* * 取り出したノードから出ている全ての辺について調べ、 暫定の最短距離が更新される場合は更新してキューに入れる */ if (dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; priorityQueue.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; } } }