BOJ 1446 지름길

www.acmicpc.net/problem/1446

1446번: 지름길

 

문제는 그리디 하게 접근해야 한다는 것이다. 그냥 지름길이 주어졌다고 해서 지금 길만 탄다면

다른 컴포넌트에 있는 길로 가는 것이 더 빠를 수 있다.

 

어떻게 접근해야 할까?

 

핵심은 다익스트라를 돌리면서 현재 위치 + 1 에 지름길이 없다면 우선순위 큐에 

cost + 1 로 넣어주는 것이다.

 

이렇게 되면 자연히 d 이하의 모든 노드를 탐색하면서 지름길이 있다면 지름길을 타고, 아니라면

다음 컴포넌트가 큐에 들어가게 된다.

 

 

if (cur + 1 <= k && d[cur + 1] > cost + 1) {
    d[cur + 1] = cost + 1;
    q.push({ -(cost + 1),cur + 1 });
}

 

k 가 고속도로의 길이 d라고 하면 현재 위치 cur + 1 이 k보다 작아야 하고(고속도로를 역주행할 수는 없기 때문에)

그다음 위치가 현 비용 + 1 보다 크다면(INF라면) 

다른 컴포넌트이기 때문에 그 위치를 큐에 넣어줘야 한다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int, int>> a[10001];
priority_queue<pair<int, int>> q;
const int inf = 1e9;
int n, k;
 
int dijkstra(int s, int e) {
    vector<int> d(10001, inf);
    q.push({ 0,s });
    d[s] = 0;
 
    while (!q.empty()) {
        auto cur = q.top().second;
        int cost = -q.top().first;
        q.pop();
        if (d[cur] < cost) continue;
        for (auto i : a[cur]) {
            int nc = cost + i.second;
            if (nc < d[i.first]) {
                d[i.first] = nc;
                q.push({ -nc,i.first });
            }
        }
        if (cur + 1 <= k && d[cur + 1] > cost + 1) {
            d[cur + 1] = cost + 1;
            q.push({ -(cost + 1),cur + 1 });
        }
    }
    return d[e];
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        int x, y, z; cin >> x >> y >> z;
        a[x].push_back({ y,z });
    }
 
    cout << dijkstra(0, k) << endl;
 
    return 0;
}