[백준] 11779 : 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

---

• 경로를 출력하는 것을 빼고는 일반적인 다익스트라 문제이다.
• 나는 경로를 단순하게 문자열로 저장해나가면서 업데이트했다.
• 현재 노드까지 최소거리인 경로를 담아놓고 갱신될때마다 새로운 경로를 저장하는 방식이다.
• 구조체 선언하고 우선순위큐를 위한 비교 구조체도 선언해서 사용하느라 조금 귀찮았다.
• 풀이를 보니, 최소 거리가 갱신될 때 노드 사이의 부모자식 관계를 설정해줌으로써 도착지점에서 부모를 타고 시작지점까지 도달하는 방법이 더 효율적인 것 같다. (마치 union-find)

---

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

#define INF 1000000000

using namespace std;

struct Node
{
    int cost;
    int city;
    string path;
};

int n, m, a, b, w, start_, end_;
vector<pair<int,int>> graph[1001];                      // 그래프 연결 정보 저장
vector<pair<int,string>> dist(1001, {INF, ""});         // 최단거리 및 경로를 저장

struct cmp
{
    bool operator()(Node& a, Node& b)                   // 우선순위큐에서 비교를 위해 사용되는 구조체
    {
        return a.cost < b.cost;
    }
};

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

    cin >> n >> m;
    for(int i = 0 ; i < m ; i++)
    {
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
    }

    cin >> start_ >> end_;

    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({0, start_, to_string(start_)});
    dist[start_].first = 0;
    while(pq.size())
    {
        int curDist = -pq.top().cost;
        int curCity = pq.top().city;
        string curPath = pq.top().path;
        pq.pop();
        if(dist[curCity].first < curDist) continue;             // 만약 최소 거리가 그 사이에 갱신되었다면 스킵

        if(curCity == end_)                                     // 목표 지점에 도달하면
        {
            cout << curDist << endl;                            // 최소 비용 출력 후
            int cnt = 1;
            for(int i = 0 ; i < curPath.size() ; i++)           // 경로에 껴있는 도시들의 개수 센 뒤 출력
            {
                if(curPath[i] == ' ') cnt++;
            }
            cout << cnt << endl;
            cout << curPath << endl;                            // 경로도 출력
        }
                                                                // 목표 지점이 아니라면
        for(int i = 0 ; i < graph[curCity].size() ; i++)        // 현재 위치에서 연결된 모든 노드들 확인
        {
            int nextCity = graph[curCity][i].first;
            int nextDist = graph[curCity][i].second + curDist;
            if(nextDist < dist[nextCity].first)                 // 최소 거리로 갱신되는 노드가 있다면
            {
                dist[nextCity].first = nextDist;                // 해당 노드 업데이트 후 pq 에 넣어줌
                dist[nextCity].second = curPath + " " + to_string(nextCity);
                pq.push({-nextDist, nextCity, dist[nextCity].second});
            }
        }
    }
}