Boj 1884 고속도로 c++

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

 

 

문제

주어진 교통비 내에서 시작점 1에서 N까지 가는 최단거리를 구하여라.

입력으로는 각각의 도로의 시작점, 도착점, 길이, 통행료가 주어진다.

교통비 내로 N에 도착할 수 없다면 -1을 출력한다.

 

 

풀이

1에서 N까지 데이크스트라를 수행하되, 주어진 통행료 내에서 도착할 수 있도록 조건을 추가해주어야 한다.

우선순위 큐에 누적거리, 노드 번호, 누적 통행료 순서로 집어 넣고, 

최단거리인 경우에는 해당 노드의 통행료를 반영하여 새로운 경로를 갱신하면 된다.

누적 통행료가 교통비를 초과하는 경우에는 큐에 넣지 않으면 된다.

 

 

풀이 코드

 

#include <bits/stdc++.h>
#define inf 999999999
using namespace std;
using pp = pair<int, pair<int, int>>;

int d[101][10001];
vector<vector<pp>> connected(101);

int main() {

    int K, N, R;

    cin >> K >> N >> R;

    for(int i = 1; i <= 100; i++)
        for(int j = 0; j <= 10000; j++)
            d[i][j] = inf;

    for(int i = 0; i < R; i++) {
        int s, d, l, t;
        cin >> s >> d >> l >> t;
        connected[s].push_back({l, {d, t}}); // 거리, 번호, 비용
    }

    priority_queue<pp, vector<pp>, greater<pp>> pq;

    pq.push({0, {1, 0}}); // 누적 거리, 현재 도시, 누적 비용
    d[1][0] = 0;

    while(!pq.empty()) {
        int dist, curr, cost;
        dist = pq.top().first;
        curr = pq.top().second.first;
        cost = pq.top().second.second;

        pq.pop();

        if(dist > d[curr][cost])
            continue;

        for(auto x : connected[curr]) {
            int next, pdist, pcost, ncost;
            pdist = x.first;
            next = x.second.first;
            pcost = x.second.second;
            ncost = cost + pcost;

            if(ncost > K)continue;

            if(d[next][ncost] > pdist + dist) {
                d[next][ncost] = pdist + dist;
                pq.push({d[next][ncost], {next, ncost}});
            }
        }
    }
    int ans = inf;

    for(int i = 0; i <= K; i++) {
        ans = min(ans, d[N][i]);
    }
    if(ans == inf)
        cout << "-1";
    else
        cout << ans;
}