結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | autotaker1984 |
提出日時 | 2015-07-18 12:41:18 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 646 ms / 5,000 ms |
コード長 | 2,857 bytes |
コンパイル時間 | 2,461 ms |
コンパイル使用メモリ | 87,432 KB |
実行使用メモリ | 61,020 KB |
最終ジャッジ日時 | 2023-09-22 18:57:40 |
合計ジャッジ時間 | 12,242 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 138 ms
55,588 KB |
testcase_01 | AC | 136 ms
55,912 KB |
testcase_02 | AC | 135 ms
56,460 KB |
testcase_03 | AC | 145 ms
55,888 KB |
testcase_04 | AC | 294 ms
60,824 KB |
testcase_05 | AC | 359 ms
60,484 KB |
testcase_06 | AC | 428 ms
60,768 KB |
testcase_07 | AC | 274 ms
60,720 KB |
testcase_08 | AC | 292 ms
58,448 KB |
testcase_09 | AC | 264 ms
59,976 KB |
testcase_10 | AC | 309 ms
61,020 KB |
testcase_11 | AC | 303 ms
61,016 KB |
testcase_12 | AC | 287 ms
60,952 KB |
testcase_13 | AC | 277 ms
60,496 KB |
testcase_14 | AC | 316 ms
60,540 KB |
testcase_15 | AC | 285 ms
60,404 KB |
testcase_16 | AC | 261 ms
60,008 KB |
testcase_17 | AC | 293 ms
60,388 KB |
testcase_18 | AC | 278 ms
60,800 KB |
testcase_19 | AC | 261 ms
60,240 KB |
testcase_20 | AC | 266 ms
60,008 KB |
testcase_21 | AC | 290 ms
60,240 KB |
testcase_22 | AC | 296 ms
60,120 KB |
testcase_23 | AC | 298 ms
60,660 KB |
testcase_24 | AC | 282 ms
60,740 KB |
testcase_25 | AC | 283 ms
60,536 KB |
testcase_26 | AC | 276 ms
60,580 KB |
testcase_27 | AC | 234 ms
59,444 KB |
testcase_28 | AC | 646 ms
60,960 KB |
testcase_29 | AC | 247 ms
59,104 KB |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int M = in.nextInt(); int S = in.nextInt(); int G = in.nextInt(); Dijkstra d = new Dijkstra(N); for( int i = 0; i < M; i++ ) { int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); d.addEdge(a,b,c); d.addEdge(b,a,c); } int[] dist = d.run(S); ArrayList<ArrayList<Edge>> g = new ArrayList<ArrayList<Edge>>(); for( int i = 0; i < N; i++ ) { ArrayList<Edge> es = new ArrayList<Edge>(); for( Edge e : d.g.get(i) ) { if( dist[e.from] + e.weight == dist[e.to] ) { es.add(e); } } g.add(es); } int v = S; while( v != G ) { System.out.print(v + " "); ArrayList<Edge> es = g.get(v); v = N; for( Edge e : es ) { if( !reachable(g,e.to,G) ) continue; v = Math.min(v, e.to); } } System.out.println(v); } static boolean reachable(ArrayList<ArrayList<Edge>> g, int s, int t){ boolean[] vis = new boolean[g.size()]; Deque<Integer> stack = new ArrayDeque<Integer>(); stack.push(s); while(!stack.isEmpty()) { int v = stack.pop(); if( v == t ) return true; if( vis[v] ) continue; vis[v] = true; for( Edge e : g.get(v) ) { stack.push(e.to); } } return false; } } class Edge implements Comparable<Edge>{ int from; int to; int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } public int compareTo(Edge e) { if( this.weight < e.weight ) return -1; if( this.weight > e.weight ) return 1; if( this.from < e.from ) return -1; if( this.from > e.from ) return 1; if( this.to < e.to ) return -1; if( this.to > e.to ) return 1; return 0; } } class Dijkstra { int N; ArrayList<ArrayList<Edge>> g; public Dijkstra(int N) { this.N = N; g = new ArrayList<ArrayList<Edge>>(); for( int i = 0; i < N; i++ ) { g.add(new ArrayList<Edge>()); } } public void addEdge(Edge e) { g.get(e.from).add(e); } public void addEdge(int from, int to, int weight) { addEdge(new Edge(from, to, weight)); } public int[] run(int start) { boolean[] vis = new boolean[N]; int[] dist = new int[N]; PriorityQueue<Edge> queue = new PriorityQueue<Edge>(); queue.add(new Edge(start,0,0)); while( !queue.isEmpty() ) { Edge e = queue.poll(); if( vis[e.from] ) continue; vis[e.from] = true; dist[e.from] = e.weight; for( Edge ne : g.get(e.from) ) { if( !vis[ne.to] ) { queue.add(new Edge(ne.to,0,ne.weight + e.weight)); } } } return dist; } }