[BOJ] 11779. 최소비용 구하기2 (C++)

문제

n개의 도시와 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다.

A번째 도시에서 B번째 도시까지 가는데 드는 최소비용과 경로 출력

생각할 것

• 다익스트라 알고리즘
  • 특정 출발지에서 특정 목적지까지의 최소비용을 구해야함
  • 가중치가 있음!
  • ⇒ 다익스트라 사용
• 최소비용은 구했지만 경로는 어떻게 알 수 있을까?
  • 다음 도시로 가기 전에 현재 도시를 저장한 뒤 역추적하기!
• priority_queue에서 pair의 second를 오름차순으로 정렬하는 방법

  • struct cmp {
        bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
            return p1.second > p2.second;
        }
    };
    
     priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits> // 헤더 안넣어서 컴파일 에러났었음 

using namespace std;

struct cmp {
    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second;
    }
};

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

    int n, m;
    cin >> n;
    cin >> m;

    vector<vector<pair<int, int>>> adj(n + 1, vector<pair<int, int>>());
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    int start, end;
    cin >> start >> end;
    vector<int> dist(n + 1, INT_MAX);
    vector<int> route(n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; // 오름차순
    dist[start] = 0;
    pq.push({start, 0}); // 목적지, 목적지까지의 거리

    while (!pq.empty()) {
        int cur = pq.top().first;
        int cost = pq.top().second;
        pq.pop();

        if (dist[cur] < cost) continue;
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i].first;
            int nextCost = cost + adj[cur][i].second; // 현재 거리에서 더하기
            if (dist[next] > nextCost) {
                route[next] = cur; // 이전 경로 저장
                dist[next] = nextCost; // 대입하는 부분 잊지않도록하기!
                pq.push({next, nextCost});
            }
        }
    }

	// 경로 역추적
    vector<int> res;
    int city = end;
    while (true) {
        res.push_back(city);
        if (city == start) break;
        else city = route[city];
    }

    cout << dist[end] << "\\n";
    cout << res.size() << "\\n";
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i] << " ";
    }

    return 0;
}