[BOJ] 11779번 최소비용 구하기 2 (C++)

문제 (https://www.acmicpc.net/problem/11779)

11779번: 최소비용 구하기 2

출발 도시에서 도착 도시까지의 최소 비용을 구하는 일반적인 다익스트라 문제이다. 다른 문제들과 차이점은 최소 비용뿐만 아니라 경로에 포함되어있는 도시의 개수와 방문하는 도시 번호도 출력해야 한다.

 

따라서 배열을 생성하여 각 도시에 도달하기 위해서는 몇 번 도시에서 출발해야 하는지를 기록했다.

예를 들어, route[a] = b는 "a번에 최소로 도달하기 위해서는 b번에서 와야 한다"라는 의미이다.

 

route[start] = 0으로 설정해주고 route[end] 값부터 역순으로 경로를 체크한다.

end 값 -> end번에 최소로 도달하기 위한 이전 번호 -> ... -> start 다음으로 방문하는 도시 번호-> start 값

역순으로 경로를 체크했으므로 reverse 함수를 사용한 후 정답을 출력했다.

---

[소스코드]

	/*
	BOJ 11779번: 최소비용 구하기 2
	2021-12-29
	*/
	#include <iostream>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#define MAX 1001
	#define INF 100000001
	using namespace std;
	int d[MAX];
	int route[MAX]; // route[a] = b: a번에 최소로 도달하기 위해서는 b 정점에서 와야 한다.
	vector<pair<int, int>> graph[MAX];
	void dijkstra(int start) {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 거리, 노드
	pq.push({0, start});
	d[start] = 0;
	while(!pq.empty()) {
	int distance = pq.top().first;
	int cur = pq.top().second;
	pq.pop();
	if(d[cur] < distance) continue;
	for(int i = 0 ; i < graph[cur].size() ; i++) {
	int newDistance = graph[cur][i].second;
	int next = graph[cur][i].first;
	if(distance + newDistance < d[next]) {
	route[next] = cur;
	d[next] = distance + newDistance;
	pq.push({d[next], next});
	}
	}
	}
	}
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	vector<int> answer;
	int n, m;
	int x, y, z;
	int start, end;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++) {
	cin >> x >> y >> z;
	graph[x].push_back({y, z});
	}
	cin >> start >> end;
	fill(d, d + n + 1, INF);
	dijkstra(start);
	route[start] = 0;
	int idx = end;
	while(1) {
	if(route[idx] == 0) {
	answer.push_back(start);
	break;
	}
	answer.push_back(idx);
	idx = route[idx];
	}
	reverse(answer.begin(), answer.end());
	cout << d[end] << '\n';
	cout << answer.size() << '\n';
	for(int i = 0 ; i < answer.size() ; i++) cout << answer[i] << " ";
	return 0;
	}

view raw 11779.cpp hosted with ❤ by GitHub

---

2021-12-29

Gold 3

- 그래프 이론

- 다익스트라