[baekjoon 11779] 최소비용 구하기2 (다익스트라) (C++)

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

11779번: 최소비용 구하기 2

최소비용 구하기 1의 업그레이드 버전이다. 추가된 것은 최소비용뿐만 아니라 최단 거리를 출력하는 것이다.

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

1916번: 최소비용 구하기

 

나는 다익스트라를 이용해서 최소비용을 계산함과 동시에, 거리가 갱신되어 우선순위 큐에 push 될 때 해당 노드의 이전 노드를 저장해주었다.

 

1 2 2

1 3 3

1 4 1

1 5 10

2 4 2

3 4 1

3 5 1

4 5 3

1 5

문제 예시인데, 보다시피 1번 노드에서 시작한다.

따라서 1번에 연결된 간선부터 다익스트라 알고리즘을 통해 체크를 할 텐데

1번과 연결된 노드 -> 2, 3, 4, 5는 모두 처음 방문하기 때문에 거리가 갱신될 것이다.

그렇게 되면

방문한 노드	1	2	3	4	5
거쳐온 노드	1	1	1	1	1

로 route 배열이 업데이트된다.

이후 우선순위 큐에서 pop 되는 노드는 4번 노드일 것이고(weight가 1로 가장 작다.)

4번과 연결된 노드는 2, 3, 5가 있고 5번 노드만 갱신이 될 것이다.(현재 가중치 10에서 1+3=4으로)

그렇게 되면

방문한 노드	1	2	3	4	5
거쳐온 노드	1	1	1	1	4

5번은 4번 노드를 통해 갱신되었으므로 4의 값을 저장하게 된다.

 

이런 식으로 다익스트라를 마무리해주고, 저장된 배열을 이용해서 역추적해준다.

1~5의 경로를 알고 싶으므로

5번의 값 -> 4, 4번의 값 -> 1 => 1 4 5의 최단 경로가 완성된다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>

#define INF 987654321

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
int N, M, from, to, weight, start, target;
vector<pii> v[1001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1001], route[1001] ;
stack<int> st;

int dijkstra(int startX, int target) {
	dist[startX] = 0;
	pq.push(make_pair(dist[startX], startX));

	while (!pq.empty()) {
		int dis = pq.top().first;
		int x = pq.top().second;
		pq.pop();

		if (x == target)
			return dist[target];


		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int weight = v[x][i].second;

			if (dist[nx] > dis + weight) {
				dist[nx] = dis + weight;
				pq.push(make_pair(dist[nx], nx));
				route[nx] = x; // 경로를 저장해준다.
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> weight;
		v[from].push_back(make_pair(to, weight));
	}
	cin >> start >> target;

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	cout<<dijkstra(start, target)<<"\n";
	
	for (int i = target; i != start; i = route[i]) // 경로 역추적 5 4 1 순서
		st.push(i);
	st.push(start);

	cout << st.size() << "\n";
	while (!st.empty()) {
		cout << st.top() << " "; // 다시 역순 출력
		st.pop();
	}

}

나는 다익스트라에서 도착점을 방문하면 바로 종료를 시켜주었다.

아마도 종료해주지 않고 모든 간선을 돌면서 최소 비용을 갱신해줄 경우 시간 초과가 나올 수도 있다.