지름길 1446

문제

접근 방법

다익스트라를 활용하여서 거리의 최솟값을 구하면 된다.

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;
typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
vector<tiii> shortPaths;
vector<int> dist;
int N, D;
priority_queue<pii, vector<pii>, greater<pii>> pq;
void dijkstra()
{
    pq.push({0, 0});
    while (!pq.empty())
    {
        pii cur = pq.top();
        pq.pop();
        int value = cur.first;
        int idx = cur.second;
        if (dist[idx] <= value)
            continue;
        dist[idx] = value;
        dist[D] = min(dist[D], dist[idx] + (D - idx));
        for (tiii shortPath : shortPaths)
        {
            int start = get<0>(shortPath);
            int end = get<1>(shortPath);
            int len = get<2>(shortPath);
            int nextValue = dist[idx] + (start - idx) + len;
            if (start < idx || dist[end] <= nextValue)
                continue;
            pq.push({nextValue, end});
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> D;
    dist = vector<int>(D + 1, 10001);
    int start, end, len;
    while (N--)
    {
        cin >> start >> end >> len;
        if (end - start < len || end > D)
            continue;
        shortPaths.push_back({start, end, len});
    }
    dijkstra();
    cout << dist[D];
    return 0;
}

풀이

D를 넘어가는 값, 가는 것이 손해인 지름길을 미리 제거해 줄 수 있다.

이후에는 각 도착지에서 D까지 그냥 가는 것이 이득인지 확인해 주고 지름길을 탈 수 있다면 우선순위 큐에 집어넣으면 된다.