백준 11779 최소비용 구하기

작성일 | In |

Problem : 최소비용 구하기

유형 : 다익스트라

문제 해석

  • A에서 B로 가는 최소 비용 거리와 경로를 찾아라.

문제 재해석

  • 최소 비용 거리 (다익스트라)
  • 경로 역추적 문제이다.

해결 전략

  • 최소 비용 거리는 다익스트라로 구한다.
  • pre 배열을 두어, 경로를 저장한다.

설계, 구현

  • pair로 { 비용, 연결된 도시 } 를 관리한다
  • 경로 역추적의 경우, 이전에 온 도시를 저장한다.
  • 5번 도시를 4번 도시를 거쳐서 올 경우가 최적인 경우
  • pre[5] = 4
  • 끝 지점 에서 부터 역추적한다.

주의할점

  • 플로이드 처럼 nxt를 이용 할경우 2차원 공간이 필요하다.
  • pre를 두어 이전에 어디서 왔는지를 기억한다.
  • 1 > 5 보다
  • 1 > 3 > 5 가 더 최적인 경우에
  • 1 이 5를 가리키고 있게 되어 문제가 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int INF = INT_MAX;
int n, m;
int st, ed;

vector<pii> node[1002];
priority_queue<pii, vector<pii>, greater<pii> >pq;
int pre[1002], cost[1002];

void Get_Answer() {
    vector<int> path;
    int cur = ed;
    while(st != cur){
        path.push_back(cur);
        cur = pre[cur];
    }
    path.push_back(cur);
    reverse(path.begin(), path.end());

    cout << cost[ed] << "\n";
    cout << path.size() << "\n";
    for (const auto it : path) {
        cout << it << " ";
    }
    cout << "\n";
}

void Dijstra() {
    pq.push({ 0,st });
    cost[st] = 0;

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

        if (cur_cost != cost[cur_idx]) continue;
        
        for (const auto &nxt : node[cur_idx]) {
            int nxt_cost = cur_cost + nxt.first;
            int nxt_idx = nxt.second;

            if (nxt_cost < cost[nxt_idx]) {
                cost[nxt_idx] = nxt_cost;
                pq.push({ nxt_cost, nxt_idx });
                pre[nxt_idx] = cur_idx;
            }

        }

    }
}


void Solve() {
    Dijstra();
    Get_Answer();
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        cost[i] = INF;
    }
}

void Input() {
    cin >> n;
    cin >> m;
    Init();

    int _st, _ed, _cost;
    while (m--) {
        cin >> _st >> _ed >> _cost;
        node[_st].push_back({ _cost , _ed });
    }
    cin >> st >> ed;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    Input();
    Solve();

    return 0;
}

피드백

  • 플로이드 워셜의 경로 추적과 다른점을 기억해두자.