結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | ぴろず |
提出日時 | 2015-02-26 18:31:54 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 686 ms / 5,000 ms |
コード長 | 3,069 bytes |
コンパイル時間 | 2,653 ms |
コンパイル使用メモリ | 83,036 KB |
実行使用メモリ | 62,244 KB |
最終ジャッジ日時 | 2024-06-23 23:50:38 |
合計ジャッジ時間 | 12,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 164 ms
55,180 KB |
testcase_01 | AC | 151 ms
54,932 KB |
testcase_02 | AC | 167 ms
55,032 KB |
testcase_03 | AC | 173 ms
55,292 KB |
testcase_04 | AC | 335 ms
60,084 KB |
testcase_05 | AC | 404 ms
60,148 KB |
testcase_06 | AC | 520 ms
60,104 KB |
testcase_07 | AC | 293 ms
59,648 KB |
testcase_08 | AC | 303 ms
59,764 KB |
testcase_09 | AC | 295 ms
59,988 KB |
testcase_10 | AC | 317 ms
59,916 KB |
testcase_11 | AC | 321 ms
61,932 KB |
testcase_12 | AC | 305 ms
59,972 KB |
testcase_13 | AC | 294 ms
60,340 KB |
testcase_14 | AC | 297 ms
59,748 KB |
testcase_15 | AC | 292 ms
59,916 KB |
testcase_16 | AC | 295 ms
60,272 KB |
testcase_17 | AC | 295 ms
60,048 KB |
testcase_18 | AC | 304 ms
60,068 KB |
testcase_19 | AC | 293 ms
59,760 KB |
testcase_20 | AC | 296 ms
60,128 KB |
testcase_21 | AC | 298 ms
59,888 KB |
testcase_22 | AC | 299 ms
59,752 KB |
testcase_23 | AC | 299 ms
59,884 KB |
testcase_24 | AC | 311 ms
60,068 KB |
testcase_25 | AC | 297 ms
59,664 KB |
testcase_26 | AC | 292 ms
60,052 KB |
testcase_27 | AC | 242 ms
57,800 KB |
testcase_28 | AC | 686 ms
62,244 KB |
testcase_29 | AC | 228 ms
56,904 KB |
ソースコード
package graph.ans2a;//http://yukicoder.me/submissions/14000 の無駄を省いた版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 n = sc.nextInt();int m = sc.nextInt();int s = sc.nextInt();int g = sc.nextInt();int[] a = new int[m];int[] b = new int[m];int[] c = new int[m];for(int i=0;i<m;i++) {a[i] = sc.nextInt();b[i] = sc.nextInt();c[i] = sc.nextInt();}ArrayList<Integer> ans = solve(n, m, s, g, a, b, c);StringBuilder sb = new StringBuilder();for(int i=0;i<ans.size();i++) {if (i > 0) {sb.append(' ');}sb.append(ans.get(i));}System.out.println(sb.toString());}public static ArrayList<Integer> solve(int n,int m,int start,int goal,int[] a,int[] b,int[] c) {Graph g = new Graph(n);for(int i=0;i<m;i++) {g.addBidirectionalEdge(a[i], b[i], c[i]);}String path = g.dijkstra(start)[goal].path;ArrayList<Integer> ans = new ArrayList<>();ans.add(start);for(int i=0;i<path.length();i++) {ans.add((int) path.charAt(i));}return ans;}}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 Dist[] dijkstra(int s) {Dist[] dist = new Dist[n];Arrays.fill(dist, Dist.INF);dist[s] = Dist.ZERO;PriorityQueue<Node> q = new PriorityQueue<Node>();q.offer(new Node(Dist.ZERO, s));while(!q.isEmpty()) {Node node = q.poll();int v = node.id;if (dist[v].compareTo(node.dist) < 0) {continue;}for(Edge e:graph[v]) {Dist d = new Dist(dist[v].dist + e.cost, dist[v].path + (char) (e.to));if (dist[e.to].compareTo(d) > 0) {dist[e.to] = d;q.add(new Node(dist[e.to], e.to));}}}return dist;}static class Edge {int to;int cost;public Edge(int to,int cost) {this.to = to;this.cost = cost;}}static class Node implements Comparable<Node>{Dist dist;int id;public Node(Dist dist,int i) {this.dist = dist;this.id = i;}public int compareTo(Node o) {return dist.compareTo(o.dist);}}static class Dist implements Comparable<Dist>{static Dist ZERO = new Dist(0,"");static Dist INF = new Dist(Graph.INF,"[");int dist;String path; //経路を無理やりStringとして保存するpublic Dist(int dist,String path) {this.dist = dist;this.path = path;}public int compareTo(Dist o) {int c1 = Integer.compare(dist, o.dist);if (c1 != 0) {return c1;}return path.compareTo(o.path);}}}