[백준] 1446 지름길

[백준] 1446 지름길

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

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, D;
	cin >> N >> D;

	//<end, <start, dist>>
	vector<pair<int, pair<int, int>>> shortCuts;

	for (int i = 0; i < N; ++i) {
		int start, end, dist;
		cin >> start >> end >> dist;

		//고속도록 역주행 불가능
		if (end > D) continue;

		//의미 없는 지름길 저장하지 않는다
		if (dist >= (end - start)) continue;

		//시작점&끝점 같은 지름길이라면 거리 최소인 것만 저장한다
		bool replaceDist = false;
		for (int i = 0; i < shortCuts.size(); ++i) {
			int shortCutEnd = shortCuts[i].first;
			int shortCutStart = shortCuts[i].second.first;

			if ((end == shortCutEnd) && (start == shortCutStart)) {
				int& shortCutDist = shortCuts[i].second.second;
				shortCutDist = min(shortCutDist, dist);
				replaceDist = true;
				break;
			}
		}
		if (!replaceDist) shortCuts.push_back({ end, {start, dist} });
	}

	//dp[pos] = 0~pos까지 운전해야하는 거리의 최솟값
	int dp[10001];
	dp[0] = 0;

	for (int pos = 1; pos <= D; ++pos) {
		dp[pos] = dp[pos - 1] + 1;
		
		//pos에서 끝나는 지름길이 있는 경우 확인
		for (int i = 0; i < shortCuts.size(); ++i) {
			int shortCutEnd = shortCuts[i].first;
			if (shortCutEnd == pos) {
				int shortCutStart = shortCuts[i].second.first;
				int shortCutDist = shortCuts[i].second.second;

				dp[pos] = min(dp[pos], dp[shortCutStart] + shortCutDist);
			}
		}
	}

	cout << dp[D];
	return 0;
}