[Baekjoon/C++] 11779번 - 최소비용 구하기 2

[백준] Baekjoon Online Judge

문제로 이동

 

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

 

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

 

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

 

---

풀이

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

#define INF 100000000

int n, m;
int sCity, eCity;
vector<pair<int, int>> bus[1001];
vector<int> last(1001);
vector<int> dist(1001, INF);

void dijkstra();

void dijkstra() {
	priority_queue<pair<int, int>> q;
	q.push({ 0, sCity });
	dist[sCity] = 0;

	while (!q.empty()) {
		int now = q.top().second;
		int cost = -q.top().first;

		q.pop();

		if (dist[now] < cost) continue;

		for (pair<int, int> ii : bus[now]) {
			int nCost = cost + ii.first;

			if (nCost < dist[ii.second]) {
				dist[ii.second] = nCost;
				last[ii.second] = now;
				q.push({ -nCost, ii.second });
			}
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		bus[a].push_back({ c, b });
	}
	cin >> sCity >> eCity;

	dijkstra();

	stack<int> s;

	s.push(eCity);
	for (int i = eCity; ; ) {
		s.push(last[i]);
		i = last[i];

		if (i == sCity) break;
	}

	cout << dist[eCity] << '\n';
	cout << s.size() << '\n';

	while (!s.empty()) {
		cout << s.top() << ' ';
		s.pop();
	}

	return 0;
}

 

#define INF 100000000

int n, m;
int sCity, eCity;
vector<pair<int, int>> bus[1001];
vector<int> last(1001);
vector<int> dist(1001, INF);

void dijkstra() {
	priority_queue<pair<int, int>> q;
	q.push({ 0, sCity });
	dist[sCity] = 0;

	while (!q.empty()) {
		int now = q.top().second;
		int cost = -q.top().first;

		q.pop();

		if (dist[now] < cost) continue;

		for (pair<int, int> ii : bus[now]) {
			int nCost = cost + ii.first;

			if (nCost < dist[ii.second]) {
				dist[ii.second] = nCost;
				last[ii.second] = now;
				q.push({ -nCost, ii.second });
			}
		}
	}
}

 데이크스트라 알고리즘으로 문제를 풀었다. 답을 출력할 때 경로도 출력해야 하기에 dist가 갱신될 때마다 last에 바로 이전에 방문한 도시의 번호를 저장하도록 했다.

 

	stack<int> s;

	s.push(eCity);
	for (int i = eCity; ; ) {
		s.push(last[i]);
		i = last[i];

		if (i == sCity) break;
	}

	cout << dist[eCity] << '\n';
	cout << s.size() << '\n';

	while (!s.empty()) {
		cout << s.top() << ' ';
		s.pop();
	}

 답을 출력하는 부분의 코드이다. 우선 도착 도시까지 가는데 드는 최소 비용인 dist[eCity]를 출력한다. 그 뒤 경로와 방문한 도시의 수를 출력하기 위해 스택에 방문한 경로를 넣는다. 그리고 스택의 size와 스택의 내용물을 출력한다.