[백준 / BOJ] C++ 11779 최소비용 구하기 2

11779번: 최소비용 구하기 2

 

문제

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

11779번: 최소비용 구하기 2

 

 

풀이

최소비용 구하기(1916번) 문제에서 확장된 문제다. 풀이는 아래 링크 참고.

https://khyunx.tistory.com/71

[백준 / BOJ] C++ 1916 최소비용 구하기

 

위 문제와 다른 점은 이동 경로를 출력해야 한다. -1 과 같이 의미 없는 수(반복문 탈출을 위해 음수로 함)로 초기화된 prev 배열을 만들어 dist 배열을 갱신할 때마다 이전 위치를 저장해준다. 그리고 다익스트라가 끝난 후 prev 배열을 end 정점부터 시작해서 역추적하면 된다.

 

 

 

코드

#include <bits/stdc++.h>
using namespace std;

#define INF 2147483647

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int N, M, s, e;
  cin >> N >> M;

  // 간선
  vector<pair<int, int>> graph[1001]; // [정점][다음 정점, 거리]
  while (M--) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back({v, w});
  }

  cin >> s >> e;

  vector<int> dist(1001, INF), visited(1001, 0), prev(1001, -1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  dist[s] = 0;          // 시작점 거리 0
  pq.push({0, s});      // 시작점만 pq에 추가
  while (!pq.empty()) { // pq가 비면 종료
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]); // curr이 방문한 정점이면 무시

    // 더 이상 방문할 수 있는 정점이 없으면 종료
    if (visited[curr])
      break;

    visited[curr] = 1; // 방문처리
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      // 거리가 갱신될 경우 pq에 추가
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        prev[next] = curr;
        pq.push({dist[next], next});
      }
    }
  }
  // 최소 비용
  cout << dist[e] << '\n';
  // 역추적
  int tmp = e;
  vector<int> ans;
  while (tmp > 0) {
    ans.push_back(tmp);
    tmp = prev[tmp];
  }
  // 경로 도시 개수
  cout << ans.size() << '\n';
  // 경로 도시
  for (int i = ans.size() - 1; i >= 0; i--)
    cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}