package graph.ans1; 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 ans = solve(n, m, s, g, a, b, c); StringBuilder sb = new StringBuilder(); for(int i=0;i 0) { sb.append(' '); } sb.append(ans.get(i)); } System.out.println(sb.toString()); } public static ArrayList 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 ans = new ArrayList<>(); int now = start; ans.add(now); while(true) { int next = 1 << 29; for(Graph.Edge e:g.graph[now]) { //nowから出てる辺全てに対して処理 if (dist[now] == dist[e.to] + e.cost) { next = Math.min(next, e.to); } } now = next; ans.add(now); if (now == goal) { break; } } return ans; } } class Graph { public static final int INF = 1<<29; int n; ArrayList[] graph; @SuppressWarnings("unchecked") public Graph(int n) { this.n = n; this.graph = new ArrayList[n]; for(int i=0;i(); } } 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 q = new PriorityQueue(); 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{ 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); } } }