[BOJ - 12763] 지각하면 안 돼(C++)

문제

접근 방법

- T 분 이내에 1 -> N 번 건물까지 M 만큼의 돈 이하로 갈 수 있다면, 최소 지출이 얼마인가?

- T 분이내에 도착할 수 있어야 함, M 이하의 돈으로 도착할 수 있어야 함

 

-> 일반적인 다익스트라 문제에서 비용이라는 제약조건이 추가된 내용

how?

= 평소에 저장하던 pair 구조가 아닌 tuple 구조 형태로 저장 -> 최소 비용을 찾아야 하므로 pq에 비용, 시간, 현재 위치로 저장하며 조건에 맞을 경우 Queue에 삽입

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
#define INF 1e9

int N, T, M, L;
vector<tuple<int, int, int>> adj[10001];

void dijkstra() {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    pq.push(make_tuple(0, 0, 1));
    vector<int> dist(N+1, INF);
    dist[0] = 0;

    while (!pq.empty()) {
        auto [cur_cost, cur_dist, cur_pos] = pq.top();
        pq.pop();

        if (cur_pos == N) {
            cout << cur_cost << '\n';
            return;
        }

        for (auto &[next_pos, next_dist, next_cost] : adj[cur_pos]) {
            int new_cost = cur_cost + next_cost;
            int new_dist = cur_dist + next_dist;

            if (new_dist <= T && new_cost <= M) {
                pq.push(make_tuple(new_cost, new_dist, next_pos));
            }
        }
    }

    cout << -1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    cin >> T >> M;

    cin >> L;

    for (int i = 1; i <= L; i++) {
        int s, e, t, c;
        cin >> s >> e >> t >> c;

        adj[s].push_back({e, t, c});
        adj[e].push_back({s, t, c});
    }
    
    dijkstra();

    return 0;
}

 

링크

12763번: 지각하면 안 돼