백준 11779 최소비용 구하기 2

문제 URL : https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

문제접근법 : 

최소비용을 구하는 문제이기 때문에 다익스트라를 이용하는 문제이지만

그경로들을 출력하는 문제입니다.

다익스트라를 어떻게 이용하면 그 경로들을 따라가야하는지 고민했더니

path 라는 배열을 만들어주고 현재가 cur 다음지점이 next라면

현재점에서 다음지점으로 최소경로를 갔을때

 

path[next]=cur로 인덱스로 활용합니다. 결국엔 시작점에서 도착지점까지 갈수있는 경로들이 나오는데

도착지점을 end라하면 path[end] 부터 역으로 추적해보면 path[index]가 0이 나오는곳이 곧 출발점이 되니 그 경로들만 따라가서 vector에 집어넣습니다. 그리고 역으로 출발했던거니 vector를 역순으로 출력하면 원래지점에서 도착지점을 출력이 가능합니다.

 

소스코드:

 

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

#include <iostream> #include <vector> #include <queue> using namespace std; int n, m; typedef pair<int, int> pp; vector<pair<int, int>> v[1001];   struct cmp{     bool operator()(pair<int, int> &a, pair<int, int> &b){         if (a.second > b.second)             return true;         return false;     } }; void dfs(int *path, int idx, vector<int> &find){     find.push_back(idx);     if (path[idx] == 0)//path가 0인지점이 출발지점     {         return;     }     dfs(path, path[idx], find); } void dijkstra(int start, int end){     int dist[1001];     int path[1001] = { 0 };//최소경로를 구하기 위한 배열     priority_queue<pp, vector<pp>, cmp> pq;     for (int i = 1; i <= n; i++)         dist[i] = 1e+9;     dist[start] = 0;     pq.push({ start, 0 });     while (!pq.empty()){         int cur = pq.top().first;         int sumcost = pq.top().second;         pq.pop();         for (int i = 0; i < v[cur].size(); i++)         {             int next = v[cur][i].first;             int nextcost = v[cur][i].second + sumcost;             if (dist[next]>nextcost){                 dist[next] = nextcost;                 pq.push({ next, nextcost });                 path[next] = cur; //이곳에 최소경로를 저장             }         }     }     cout << dist[end] << "\n";     vector<int> result;     dfs(path, end, result);//최소경로를 역추적함     cout << result.size() << "\n";     for (auto it = result.rbegin(); it != result.rend(); it++)//역추적에서 담은걸 역으로 출력해줌         cout << *it << " ";     cout << "\n"; } int main() {     cin >> n >> m;     for (int i = 0; i < m; i++)     {         int x, y, z;         cin >> x >> y >> z;         v[x].push_back({ y, z });     }     int start, end;     cin >> start >> end;     dijkstra(start, end);   } Colored by Color Scripter

cs

 

모르는거나 궁금한점이 있으시다면 언제든 댓글을 이용해주시길 바랍니다.