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

BOJ No.11779 [최소비용 구하기2]

---

 Problem 

11779번: 최소비용 구하기 2

---

 Code 

#include <iostream>
#include <queue>
#include <vector>
#define cost first
#define ver second
 
using namespace std;
typedef pair<int, int> PII;
typedef unsigned long long ull;
 
int V, E;
int from, to;
const ull INF = 9000000000000000000;
vector<vector<PII>> node;
 
void solved(int from, int to) {
    vector<ull> cost_to(V + 1, INF);
    vector<queue<int>> sequence(V + 1);
    priority_queue<PII, vector<PII>, greater<PII>> pq;
 
    cost_to[from] = 0;
    pq.push(PII(cost_to[from], from));
    sequence[from].push(from);
 
    while (!pq.empty()) {
        PII cur = pq.top();
        pq.pop();
 
        if (cur.cost > cost_to[cur.ver]) continue;
        
        for (int i = 0; i < node[cur.ver].size(); i++) {
            PII next = node[cur.ver][i];
            next.cost += cur.cost;
 
            if (cost_to[next.ver] > next.cost) {
                sequence[next.ver] = sequence[cur.ver];
                sequence[next.ver].push(next.ver);
 
                cost_to[next.ver] = next.cost;
                pq.push(next);
            }
        }
    }
 
    cout << cost_to[to] << '\n';
    cout << sequence[to].size() << '\n';
 
    int seqSize = sequence[to].size();
 
    while (seqSize--) {
        cout << sequence[to].front() << ' ';
        sequence[to].pop();
    }
}
 
int main() {
    cin >> V >> E;
    node.resize(V + 1);
 
    for (int i = 0; i < E; i++) {
        int s, e, cst;
        cin >> s >> e >> cst;
 
        node[s].push_back(PII(cst, e));
    }
 
    cin >> from >> to;
 
    solved(from, to);
}

---

 How to solve 

출력 조건

  출력 조건의 둘째, 셋째 조건이 없다면 그냥 정말 기본적인 다익스트라 문제이며, 1916번: 최소비용 구하기 가 이에 해당한다.

 

  기존 다익스트라의 형태에 #18 line 과 같이 sequence[ i ]를 선언해 주었다.

vector<queue<int>> sequence(V + 1);

• sequence[ i ] : vertex from 부터 vertex i 까지 가는 최소 비용 경로를 담는 queue 이다.

    #23, #36 ~ #37 에서 sequence에 대해 최신화를 해준다.

 

• #23 : vertex from 에서 vertex from 까지 sequnce인 sequence[from] 에 vertex from 을 push 해준다.
• #36 ~ #37 : 현재까지의 cost_to[next.ver] 보다 cur.ver을 경유하고 next.ver에 가는 cost인 next.cost가 더 작을 경우 sequence[next.ver]를 업데이트 해준다. 업데이트는, sequence[next.ver]를 sequence[cur.ver]에 next.ver를 하나 더 push되도록 업데이트 해주면 된다.

  그리고 둘째 셋째 조건은, sequence[to]의 크기, 그리고 sequence[to]를 front(), pop()을 해 가면서 프린트 하면 된다.