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

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

1446번: 지름길

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, D;
vector<pii>v[10001];
int dist[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> D;
    for(int i=0; i<N; i++)
    {
        int s, e, cost;
        cin >> s >> e >> cost;
        v[e].push_back({s, cost});
    }

    for(int i=0; i<10001; i++) dist[i]=MAX;
    dist[0]=0;

    for(int i=1; i<=D; i++)
    {
        dist[i]=dist[i-1]+1; //지름길이 없다면
        for(int j=0; j<v[i].size(); j++)
        {
            dist[i] = min({dist[i], dist[v[i][j].first] + v[i][j].second}); //지름길이 있다면 (직전값 + 1, 지름길 이용) 값 비교
        }
    }

    cout << dist[D];
 
}

 

다익스트라 알고리즘과 유사한 문제이다.

입력받는 부분, 초기화 값을 MAX로 두고 시작하는 부분, 시작 값을 0으로 초기화하는 부분까지는 동일하다.

 

여기서 지름길만 존재하는 것이 아니라 평범하게 이동하는 방법도 있으므로 이것을 고려해주어야 한다.

평범하게 이동하는 경우 직전 값 + 1로 값을 설정해준다.

지름길이 존재한다면 연결된 위치의 값 + 현재 위치에 대한 값을 해주어 지름길에 대한 값을 설정해준다.

 

해당 값을 담는 dist 배열을 위 2가지의 값을 계속해서 비교해주며 목표 총 길이인 D에 도달했을 때 저장된 최소값을 출력해준다.