BOJ 11779 : 최소비용 구하기 2 [C++]

 

11779번: 최소비용 구하기 2

 

최소비용 문제라 바로 다익스트라부터 떠올렸다.

다익스트라를 적용하되, 최소 비용을 갖는 경로도 출력해야 하기 때문에

각 노드의 최소 거리를 담는 dist를 '최소 거리, 어느 노드에서 왔는지'로 구성했다.

다익스트라를 수행 후, 도착지부터 어디서 왔는지 따라가며 노드를 스택에 저장하고,

출발지는 '어디서 왔는가'를 -1로 표현해 다음 노드가 -1이면 멈추도록 해 경로를 저장했다.

이후 스택을 차례로 뽑으면 출발지부터 도착지까지의 경로를 출력할 수 있다.

 

처음 코드를 작성하고 예제를 돌렸을 때, 예제 출력과 달리 경로가 '1 4 5'가 나왔다.

입력의 구성을 보니 '1 3 5', '1 4 5' 모두 같은 비용의 경로였는데, 스페셜 저지 딱지가 붙어있는 것을 보고

'작은 노드를 우선으로 채용하는건가'라고 생각하여 코드를 수정했다.

(문제 해결 후 질문 게시판을 보니 꼭 이런 건 아닌 것 같다. '1 4 5'가 나오는 코드가 통과된다고 한다.)

거리 비교 대상 노드에 대해 거리가 같은데 이전 노드의 번호가 기존에 저장된 노드의 번호보다 작다면

최신화하도록 코드를 추가했다.

 

그러나 시간 초과가 나서 '1916 : 최소 비용 구하기' 문제 코드를 참고했다.

해당 문제에선 다익스트라를 수행하기 전, 각 노드의 간선 정보를 비용이 작은 순으로 정렬 후 사용하여

시간을 줄였다.

이를 여기 적용해 통과할 수 있었다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_COST 2000000000

std::vector<std::pair<int, int>> edges[1001];
std::pair<long long, int> dist[1001];
std::stack<int> ans;

void dijkstra(int departure) {
    dist[departure] = {0, -1};
    std::priority_queue<std::pair<long long, int>> pq;
    pq.push({0, departure});

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        long long cur_dist = -pq.top().first;
        pq.pop();

        for (int i = 0; i < edges[cur_node].size(); i++) {
            int next_node = edges[cur_node][i].first;
            long long next_dist = edges[cur_node][i].second + cur_dist;

            if (next_dist == dist[next_node].first && cur_node < dist[next_node].second) {
                dist[next_node] = {next_dist, cur_node};
            }
            if (next_dist < dist[next_node].first) {
                dist[next_node] = {next_dist, cur_node};
                pq.push({-next_dist, next_node});
            }
        }
    }
}

bool cmp(std::pair<int, int> a, std::pair<int, int> b) {
    return (a.second < b.second);
}

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

    int n = 0;
    std::cin >> n;

    for (int i = 1; i < n + 1; i++) {
        dist[i] = {MAX_COST, -1};
    }

    int m = 0;
    std::cin >> m;

    for (int i = 0; i < m; i++) {
        int start = 0, end = 0, cost = 0;
        std::cin >> start >> end >> cost;
        edges[start].push_back({end, cost});
    }

    for (int i = 1; i < n + 1; i++) {
        std::sort(edges[i].begin(), edges[i].end(), cmp);
    }

    int departure = 0, arrival = 0;
    std::cin >> departure >> arrival;

    dijkstra(departure);

    int next_node = arrival;
    while (next_node != -1) {
        ans.push(next_node);
        next_node = dist[next_node].second;
    }

    std::cout << dist[arrival].first << "\n";
    std::cout << ans.size() << "\n";

    while (!ans.empty()) {
        std::cout << ans.top() << " ";
        ans.pop();
    }

    return 0;
}