結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2015-07-18 12:41:18 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 739 ms / 5,000 ms |
コード長 | 2,857 bytes |
コンパイル時間 | 2,576 ms |
コンパイル使用メモリ | 80,956 KB |
実行使用メモリ | 49,788 KB |
最終ジャッジ日時 | 2024-07-08 10:08:40 |
合計ジャッジ時間 | 12,973 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
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; } }