백준 - 1446번 : 지름길 (C++)

풀이 방법 : DP

입력으로 주어지는 대로 단방향 그래프를 하나 만들고 1에서부터 출발해서 거리 계산해주며 최단거리를 갱신해주면 된다.
예시 입력을 보니 지름길의 도착지점이 입력으로 주어지는 D보다 큰 경우가 있길래 이 경우는 건너 뛰도록 해주었다.

#include <iostream>
#include <vector>

using namespace std;

int DP[10001] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

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

	vector<vector<pair<int, int>>> vecDist(D + 1);

	for (int i = 0; i < N; ++i)
	{
		int Src, Dest, Dist;
		cin >> Src >> Dest >> Dist;

		if (Dest > D)
			continue;

		pair<int, int> Info;
		Info.first = Src;
		Info.second = Dist;

		vecDist[Dest].push_back(Info);
	}

	for (int i = 1; i <= D; ++i)
	{
		DP[i] = DP[i - 1] + 1;
		int Size = vecDist[i].size();

		for (int j = 0; j < Size; ++j)
		{
			int Src = vecDist[i][j].first;
			int Dist = vecDist[i][j].second;

			DP[i] = min(DP[i], DP[Src] + Dist);
		}
	}


	cout << DP[D];
}