[백준] 11779 최소 비용 구하기2(C++)

11779번: 최소비용 구하기 2 (acmicpc.net)

11779번: 최소비용 구하기 2

---

난이도 : 골드 3

 

풀이 방법 :

다익스트라를 이용하는 문제 

경로를 출력하는 것이 관건이었다...

경로를 출력하는 방법을 도시 개수만큼 배열(route)을 선언해 주고

다익스트라에서 dist(비용) 이 업데이트 될 때, 업데이트 되는 next인덱스에 전 노드 here 값을 저장 시켜준다.

그러면 route배열의 각 인덱스에는 인덱스 전의 노드의 인덱스 가 저장 되어 있는 것임

 

그래서 도착번호의 인덱스를 따라가다보면 경로가 나오게 된다 그걸 벡터에 저장함 

말로 설명하니까 좀 이상한데 코드 보면 이해 될거같네요

 

 

코드 : 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> 
#define INF 1e9
using namespace std;

int n, m, st, ed, route[1003];
vector<pair<int, int>> v[1003];
vector<int> ans;	
int main() {
	cin >> n >> m;

	int x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
	}

	cin >> st >> ed;
	vector<int> dist(n+1, INF);
	dist[st] = 0;
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, st));


	while (!q.empty()) {
		pair<int, int> cur = q.top();
		int here = cur.second;
		int cost = -cur.first;

		//cout << here << " ";
		q.pop();

		if(cost > dist[here]) continue;
		if (here == ed) break;

		for (int i = 0; i < v[here].size(); i++) {
			int next = v[here][i].first;
			int nextcost = v[here][i].second;

			if (dist[next] > nextcost + cost) {
				route[next] = here; //만약에 업데이트 되면 route에 저장되는 값은 전 인덱스 값이다.
				dist[next] = nextcost + cost;
				
				q.push(make_pair(-dist[next], next));
			}
		}

	}

	cout << dist[ed] << "\n";
	
	int t = ed;
	while (t) {
		ans.push_back(t);
		t = route[t]; //route에 저장 된 값은 전 인덱스 값이므로 t가 0이 될때까지 경로를 찾음
	}
	cout << ans.size() << "\n";

	for (int i = ans.size() - 1; i >= 0; i--) {
		cout << ans[i] << " ";
	}
}