Algorithm & Data Structures/BOJ
11779. 최소비용 구하기2 (Java)
Geisha
2023. 11. 7. 14:24
다익스트라 문제에 다가
자료구조 한두개를 더 추가하여
다익스트라 로 경유한 정점과 정점의 갯수를 출력하는 문제였다.
package algorithm.src.minho;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node implements Comparable<Node>{
int end;
int val;
public Node(int end, int val) {
super();
this.end = end;
this.val = val;
}
@Override
public int compareTo(Node o) {
return this.val-o.val;
}
}
public class b11779 {
static int N ; // 도시의 갯수 (정점)
static int M ; // 버스의 갯수 (간선)
static ArrayList<Node>[] list;
static int[] dist;
static int INF = Integer.MAX_VALUE;
static ArrayList<Integer>[] city;
static boolean[] isVisited;
static void Dijkstra(int s, int e) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(s,0));
dist[s] = 0;
while(!pq.isEmpty()) {
Node now = pq.poll();
if(isVisited[now.end]) continue;
isVisited[now.end] = true;
for(Node next:list[now.end]) {
if(dist[next.end]>dist[now.end]+next.val) {
dist[next.end]=dist[now.end]+next.val;
city[next.end]=(ArrayList<Integer>) city[now.end].clone();
city[next.end].add(now.end);
pq.add(new Node(next.end,dist[next.end]));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
list = new ArrayList[N+1];
city = new ArrayList[N+1];
dist = new int[N+1];
isVisited = new boolean[N+1];
for(int i = 1 ; i <= N ; i++) {
list[i] = new ArrayList<>();
dist[i] = INF;
city[i] = new ArrayList<>();
}
for(int i = 0 ; i < M ; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list[a].add(new Node(b,v));
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int arrive = Integer.parseInt(st.nextToken());
Dijkstra(start,arrive);
System.out.println(dist[arrive]);
System.out.println(city[arrive].size()+1);
for(int a : city[arrive]) {
System.out.print(a+" ");
}
System.out.println(arrive);
}
}