<백준> 1446번 지름길

<링크>

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

 

<문제>

• 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다.
• 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다.
• 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다.
• 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.
• 세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

<입력>

• 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다.
• N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다.
• 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다.
• 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다.
• 지름길의 시작 위치는 도착 위치보다 작다.

<출력>

• 세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

 

<아이디어>

1. 최솟값이니까 먼저 떠오른건 다익스트라! 플로이드-워샬!! 근데.. 이건 모든 쌍을 찾을 필요는 없기 때문에, 다익스트라를 쓰겠소..

2. 다 익스트라를 쓰기 위한 Node를 선정해주어야 합니다..!

3. 비교하면서 마지막에 D 친구를 출력하면 되는데, 값 갱신할때, D를 넘어가는 범위가 있을수도있으니... 반드시 그부분도 같이 판별해야해요!!

<풀이 - JAVA>

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

public class M_1446 {

	private static class Node {
		public int start;
		public int end;
		public int weight;

		public Node(int start, int end, int weight) {
			super();
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Node [start=" + start + ", end=" + end + ", weight=" + weight + "]";
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] split = in.readLine().split(" ");
		//지름길 수
		int N = Integer.parseInt(split[0]);
		// 고속도로 길이
		int D = Integer.parseInt(split[1]);

		// 도로 최단거리 배열
		int[] distances = new int[D + 1];
		Arrays.fill(distances, Integer.MAX_VALUE);
		distances[0] = 0;

		// 지름길 저장
		Node[] nodes = new Node[N];
		for (int i = 0; i < N; i++) {
			split = in.readLine().split(" ");
			int from = Integer.parseInt(split[0]);
			int to = Integer.parseInt(split[1]);
			int len = Integer.parseInt(split[2]);
			// 각 노드에 담기
			nodes[i] = new Node(from, to, len);
		}

		// 거리 계산
		for (int i = 0; i < D; i++) {
			// 고속도로를 탄거랑, 한칸 움직이는거랑 비교했을때 작은 녀석이 더 좋은 녀석!
			distances[i + 1] = Math.min(distances[i + 1], distances[i] + 1);

			// 지름길 확인
			for (Node node : nodes) {
				if (node.start == i && node.end <= D) {
					// 지름길이나 가셈.
					distances[node.end] = Math.min(distances[node.end], distances[i] + node.weight);
				}
			}
		}

		System.out.println(distances[D]);

	}

}