[백준 1446] 지름길 (C++)

문제 링크: www.acmicpc.net/problem/1446

1446번: 지름길

1. 주의할 점

- 최단거리가 지름길을 안탈수도 있는 경우가 있다

 

2. 구현

- Dist[]를 통해 0부터 각 지점까지의 길이를 미리 저장한다

- 지름길에 대한 정보를 받을 때, 지름길의 도착지점이 목표지점을 넘어가거나, 사실상 지름길이 아닌 경우는 제외한다

- 0부터 도착지점까지 Dist[] 배열을 갱신하며, 만약 해당 지점에 지름길이 있는 경우, 지름길의 반대편까지의 거리를 기존 길이와 비교하여 지름길을 사용했을 때 더 짧다면 Dist[]를 갱신한다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct info{
    int idx,val;
};
info tmp;
int dist[10001];
vector<info> v[10001];
int main() {
    int num, goal,s,e,val,before;
    cin>>num>>goal;
    for(int i=1;i<=goal;i++)
        dist[i]=i;
    for(int i=0;i<num;i++){
        cin>>s>>e>>val;
        if(e-s<=val) continue;      //사실상 지름길이 아닌 경우
        if(e>goal) continue;        //목적지를 넘어가는 경우 -> 역주행 불가
        tmp.idx=e;
        tmp.val=val;
        v[s].push_back(tmp);
    }
    for(int i=0;i<=goal;i++){
        if(i==0) before = -1;
        else before = dist[i-1];
        dist[i]=min(dist[i],before+1);
        if(!v[i].empty()){
            for(int k=0;k<v[i].size();k++){
                int to = v[i][k].idx;
                int cost = v[i][k].val;
                if(to>goal) continue;
                if(dist[i]+cost<dist[to]){
                    dist[to] = dist[i] + cost;
                }
            }
        }
    }
    cout<<dist[goal];
    return 0;
}