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

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

728x90

반응형

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

풀이

1916번 최소비용구하기의 코드에 몇가지만 추가를 해주면 된다.

https://khu98.tistory.com/237

다익스트라를 실행시키면서 최소비용이 갱신되는 노드가 있다면, 추적을 도와주는 trace배열에 자신 이전의 노드를 추가를 해준다. 다익스트라를 모두 실행시킨뒤, 도착지점부터 시작지점까지 trace를 이용하여 역추적을 한뒤, 그 결과를 reverse함수를 이용해서 거꾸로 출력시켜주면된다.

코드

#include #include #include #include #include #define MAX 987654321 using namespace std; vector> maze[1001]; int cost[1001]; int trace[1001]; bool visited[1001] = { 0 }; int n, m,st,en; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cost[i] = MAX; } for (int i = 0; i < m; i++) { int to, from, cost; cin >> to >> from >> cost; maze[to].push_back({ from,cost }); } cin >> st >> en; priority_queue> pq; cost[st] = 0; trace[st] = -1; pq.push({ 0,st }); while (!pq.empty()) { int now = pq.top().second; int dist = -pq.top().first; pq.pop(); if (cost[now] < dist) continue; for (auto next : maze[now]) { int next_node = next.first; int next_cost = next.second; if (cost[next_node] > next_cost + dist) { cost[next_node] = next_cost + dist; trace[next_node] = now; pq.push({ -(next_cost + dist),next_node }); } } } vector result; result.push_back(en); int now_node = en; while (trace[now_node] != -1) { result.push_back(trace[now_node]); now_node = trace[now_node]; } reverse(result.begin(), result.end()); cout << cost[en] << "

" << result.size() << "

"; for (int i = 0; i < result.size(); i++) { cout << result[i] << " "; } return 0; }

반응형

from http://khu98.tistory.com/238 by ccl(A) rewrite - 2021-08-18 02:00:16