[백준(Baekjoon)][자바(java)] 11779 : 최소비용 구하기 2 / 동적 계획법과 최단거리 역추적

 

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static class Path implements Comparable<Path> {
		int v, d, cnt; // vertex num, cost from start vertex, cnt of cities visited
		Path(int v, int d, int cnt) {
			this.v = v;
			this.d = d;
			this.cnt = cnt;
		}
		@Override
		public int compareTo(Path o) {
			return d - o.d;
		}
	}

	static class Node {
		int v, w; // vertex_connected num, weight
		Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
		int u, v, w, start, end, i;
		List<List<Node>> e = new LinkedList<>();
		StringTokenizer st;
		for (i = 0; i < n; i++)
			e.add(new LinkedList<Node>());
		for (i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			w = Integer.parseInt(st.nextToken());
			e.get(u).add(new Node(v, w));
		}
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken()) - 1;
		end = Integer.parseInt(st.nextToken()) - 1;
		br.close();

		int cost[] = new int[n], d_u, d_v, cnt_u, cnt_v;
		int[] dp_v = new int[n], dp_cnt = new int[n]; // previous vertex num
		// boolean visited[] = new boolean[n];
		// visited[start] = true;
		for (i = 0; i < n; i++)
			cost[i] = Integer.MAX_VALUE;
		cost[start] = 0;

		PriorityQueue<Path> pq = new PriorityQueue<>();
		pq.add(new Path(start, 0, 1));
		while (!pq.isEmpty()) {
			Path p = pq.remove();
			u = p.v; d_u = p.d;
			if (cost[u] < d_u) continue;
			cnt_u = p.cnt; cnt_v = cnt_u + 1;
			for (Node nd : e.get(u)) {
				v = nd.v; // connected vertex num
				w = nd.w; // connected weight
				d_v = d_u + w;
				if (cost[v] > d_v) {
					pq.add(new Path(v, d_v, cnt_v));
					cost[v] = d_v;
					dp_v[v] = u;
					dp_cnt[v] = cnt_v;
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		int path = end, cnt = dp_cnt[end]; i = 0;
		sb.append(path + 1);
		while (++i < cnt) 
			sb.insert(0, ((path = dp_v[path]) + 1) + " ");
		sb.insert(0, dp_cnt[end] + "\n");
		sb.insert(0, cost[end] + "\n");

		System.out.println(sb.toString());
	}

}