240528 지름길

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());

	int n = Integer.parseInt(st.nextToken());
	int len = Integer.parseInt(st.nextToken());

	int[] memo = new int[len + 1];
	for (int i = 0; i <= len; i++) {
		memo[i] = i;
	}

	int[][] road = new int[n][3];
	for (int i = 0; i < n; i++) {
		st = new StringTokenizer(br.readLine());
		road[i][0] = Integer.parseInt(st.nextToken());
		road[i][1] = Integer.parseInt(st.nextToken());
		road[i][2] = Integer.parseInt(st.nextToken());
	}

	for (int i = 0; i <= len; i++) {
		if (i > 0) {
			memo[i] = Math.min(memo[i], memo[i - 1] + 1);
		}
		for (int j = 0; j < n; j++) {
			if (road[j][1] == i) {
				if (road[j][2] < road[j][1] - road[j][0]) {
					memo[i] = Math.min(memo[road[j][0]] + road[j][2], memo[i]);
				}
			}
		}
	}

	System.out.println(memo[len]);
}

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