백준 11779 풀이
최소비용 구하기 2
https://www.acmicpc.net/problem/11779
풀이
기존의 최소비용 구하기?와 동일하게 다익스트라 알고리즘을 이용해 최소비용을 구한다. 하지만 문제에서 경로와 거치는 정거장의 수도 출력해야 하기때문에 다익스트라 알고리즘 과정에 하나를 더 추가한다.
route 라는 1차원 배열을 만들고 여기에 출발한 노드의 번호를 집어넣는다.
dist 배열에서 비용이 갱신될 때 route 배열에도 출발한 노드의 번호를 넣게되면 도착지에서 출발지로 역추적이 가능하다.
이를 스택으로 정리하여 출력하면 경로가 나오고, 스택의 사이즈가 거친 정거장의 수이다.
코드
import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;
public class Main {
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
static int n, m;
static ArrayList<Pair>[] graph;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//String[] input = br.readLine().split(" ");
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++)
graph[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
String[] line = br.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
graph[x].add(new Pair(y, w));
}
String[] last = br.readLine().split(" ");
int start = Integer.parseInt(last[0]);
int dest = Integer.parseInt(last[1]);
Entry result = dijkstra(start);
int[] dist = result.dist;
int[] route = result.route;
System.out.println(dist[dest]);
Stack<Integer> s = new Stack<>();
int temp = dest;
s.push(temp);
while (true) {
int k = route[temp];
s.push(k);
if(k == start) {
break;
}
temp = k;
}
System.out.println(s.size());
while(!s.isEmpty())
System.out.print(s.pop() + " ");
bw.close();
br.close();
}
private static Entry dijkstra(int start) {
int[] dist = new int[n + 1];
int[] route = new int[n + 1];
boolean[] visit = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if (i == start) {
dist[i] = 0;
route[i] = 1;
}
else
dist[i] = Integer.MAX_VALUE;
}
PriorityQueue<Pair> queue = new PriorityQueue<>();
queue.offer(new Pair(start, 0));
while (!queue.isEmpty()) {
Pair p = queue.poll();
int y = p.dest;
if (visit[y])
continue;
else
visit[y] = true;
for (Pair next : graph[y]) {
if (dist[next.dest] >= dist[y] + next.weight) {
dist[next.dest] = dist[y] + next.weight;
route[next.dest] = y;
queue.offer(new Pair(next.dest, dist[next.dest]));
}
}
}
return new Entry(dist, route);
}
}
class Entry {
public int[] dist;
public int[] route;
public Entry(int[] dist, int[] route) {
this.dist = dist;
this.route = route;
}
}
class Pair implements Comparable<Pair> {
public int dest;
public int weight;
public Pair(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Pair o) {
return Integer.compare(this.weight, o.weight);
}
}
Author And Source
이 문제에 관하여(백준 11779 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-11779-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)