[BOJ - 23033] 집에 빨리 가고 싶어! (C++)

문제

접근방법

 방향성이 존재하고 최단 경로를 탐색 -> 다익스트라 알고리즘을 사용

 대기 시간이 존재 -> 걸리는 시간에 대기 시간을 추가하는 로직을 추가

if (cur_time % interval != 0) wait = interval - (cur_time % interval);

 

코드

#include <iostream>
#include <queue>
#include <vector>

#define INF 1e9

using namespace std;

int N, M;
vector<pair<int, pair<int, int>>> adj[20001];


int dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(N+1, INF);

    dist[1]=0;
    pq.push({0, 1});
    while(!pq.empty()) {
        auto [cur_time, cur] = pq.top(); pq.pop();

        if (dist[cur] < cur_time) continue;

        for (auto [next, info]: adj[cur]) {
            int travel_time = info.first;
            int interval = info.second;

            int wait = 0;
            if (cur_time % interval != 0) wait = interval - (cur_time % interval);

            int next_time = cur_time + wait + travel_time;
            if (next_time < dist[next]) {
                dist[next] = next_time;
                pq.push({next_time, next});
            }
        }
    }

    return dist[N];
}

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

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int A, B, T, W;
        cin >> A >> B >> T >> W;
        adj[A].push_back({B, {T, W}});
    }

    cout << dijkstra() << "\n";

    return 0;
}

 

링크

23033번: 집에 빨리 가고 싶어!