[BaekJoon][1446] 지름길

BAEKJOON ONLINE JUDGE

1446 지름길

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
#define Min(x, y)        (((x) < (y)) ? (x) : (y))
 
struct Road {
    int start, end, length;
};
 
int n, d;
Road road[10001];
int dp[10001];
 
bool cmp(const Road &first, const Road &second)
{
    if (first.start == second.start)    return first.end < second.end;
    return first.start < second.start;
}
 
void input()
{
    scanf("%d %d", &n, &d);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &road[i].start, &road[i].end, &road[i].length);
    }
}
 
int solve()
{
    int total = 0;        // 움직여서 있는 현재 위치
    int ans = 0;
    int idx = 0;
 
    for (int i = 0; i <= d; i++) {
        dp[i] = 1e9;
    }
 
    sort(road, road + n, cmp);
 
    dp[0] = 0;
    while (total != d) {
        if (total == road[idx].start) {
            if (road[idx].length <= d) {
                dp[road[idx].end] = Min(dp[total] + road[idx].length, dp[road[idx].end]);
            }
            else {
                dp[d] = total + d - total;
            }
            idx++;
        }
        else {
            dp[total + 1] = Min(dp[total + 1], dp[total] + 1);
            total++;
        }
    }
 
    return dp[d];
}
 
int main()
{
    input();
 
    printf("%d\n", solve());
 
    return 0;
}