[boj] 백준 1446 지름길 - 다익스트라

[문제]

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

1446번: 지름길

 

[풀이]

다익스트라 최단 거리 문제이다.

먼저 지름길의 시작위치, 도착위치, 길이를 입력받을 때, (도착위치-시작위치)보다 지름길 전체 길이가 더 긴 경우에는 지름길의 의미가 없다. 또한 역주행이 불가능하므로 도착위치가 D를 넘어서면 안된다. 이 두가지 경우를 제외하고 벡터에 저장해준다.

그 후, 그래프를 계속 최단 거리로 갱신해준다. 예를 들어 (0, 50, 10) (50, 100, 10)에 대해 i=0일 때, dist[50](50)  > dist[0](0) + 10 이므로 dist[50]이 10으로 갱신되고, dist[100](100) > dist[50](10) + 10 이므로 dist[100]이 20으로 갱신된다. 그 후 dist[101]은 101보다 20+1이 더 작으므로 21로 갱신된다. dist[150]까지 더 남은 지름길이 없으므로 그대로 1씩 더해져 70이 최단거리가 된다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

struct Edge{
    int w, cost;
};

int main() {
    //운전해야 하는 거리의 최솟값
    //지름길의 개수 N 고속도로의 길이 D
    //지름길의 시작위치, 도착위치, 지름길의 길이
    int N, D;
    cin >> N >> D;
    int dist[10001];
    vector<Edge> graph[10001];
    for(int i=0; i<=D; i++){
        dist[i] = i;
    }

    int v, w, cost;
    for(int i=0; i<N; i++){
        cin >> v >> w >> cost;
        if(w-v <= cost) continue; //지름길 의미 없음.
        if(w > D) continue; //도착지점이 d를 넘어가는 경우
        graph[v].push_back({w, cost});
    }

    int prev;
    for(int i=0; i<=D; i++){
        if(i)
            prev = dist[i-1];
        dist[i] = min(dist[i], prev+1);

        for(auto e: graph[i]){
            if(dist[e.w] > dist[i] + e.cost){
                dist[e.w] = dist[i] + e.cost;
            }
        }
    }

    cout << dist[D];

}