백준 11779 최소비용 구하기 2 (c++) : 피너클

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

11779번: 최소비용 구하기 2

다익스트라문제다.

다익스트라는 다른 블로그에서 많이 찾아볼수 있으니 생략하고 문제는 경로를 저장하는 것이다.

int n, m;
int dist[1001];
int s, e;
vector<pair<int, int>> graph[1001];
vector<int> way[1001];

입력받을 변수들을 선언해주고 경로를 저장할 벡터 way를 선언했다.

cin >> n >> m;
for (int i = 0; i < m; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	graph[a].push_back({ b, c });
}
cin >> s >> e;
dijkstra();

값들을 입력받은 뒤 다익스트라를 실행한다.

다익스트라는 현재 경로보다 더 좋은 경로가 있으면 그 경로로 업데이트하는 알고리즘이다.

void dijkstra() {
	for (int i = 0; i < 1001; i++) dist[i] = 987654321;
	way[s].push_back(s);
	priority_queue<pair<int, int>> pq;
	dist[s] = 0;
	pq.push({ 0, s });

다익스트라 함수다.

dist를 초기화 하고 way[s]에 s를 넣는다.

그후 priority_queue를 선언하고 dist[s]를 0으로 바꾼뒤 pq에 {0, s)를 넣는다.

dist[s]를 0으로 바꾼 이유는 dist[i]가 의미하는 것이 s에서 i까지 걸리는 최소 거리이기 때문이다.

우리집에서 우리집까지 가는데 0초가 걸리듯이 dist[s]를 0으로 초기화하는것이다.

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

그후 pq가 비어있지 않는동안 반복문을 돌린다.

cost는 현재 정점까지 오는데 필요한 비용, now는 현재 정점이다.

	if (dist[now] < cost) continue;

만약 s에서 now까지 오는 비용보다 cost가 크다면 뒤는 볼 필요가 없으니 다 무시해준다.

	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i].first;
		int nextCost = graph[now][i].second;

그후 현재 정점에서 갈수있는 모든 정점들을 돌아본다.

next는 현재 정점에서 갈수있는 다음 정점, nextCost는 현재정점에서 다음정점까지 가는데 드는 비용이다.

		if (cost + nextCost < dist[next]) {

만약 현재 정점까지의 비용 + 현재 정점에서 다음 정점까지의 비용 이 현재 저장된 다음 정점까지의 비용보다 작다면

			dist[next] = cost + nextCost;
			pq.push({ -(cost + nextCost), next });
			way[next].clear();
			for (int j = 0; j < way[now].size(); j++) way[next].push_back(way[now][j]);
			way[next].push_back(next);

먼저 dist[next]를 업데이트 해준뒤

pq에 값들을 넣어준다. -를 하는 이유는 우선순위를 낮추기 위해서다.

비용이 적은 경로가 우선순위가 높아야 하는데 일반적인 pq에서는 높은 값이 우선순위를 갖는다.

그러니 -처리를 해서 높은 숫자의 우선순위를 낮추고 낮은 숫자의 우선순위를 높이는 것이다.

그후 way[next]를 전부 없엔다. 기존의 경로보다 더 좋은 경로가 나타났기 때문이다.

더 좋은 경로는 [현재 정점 + 다음 정점]의 경로다.

way[next]에 way[now]경로를 모두 집어넣고 마지막에 next를 집어넣는다.

 

dijkstra();
cout << dist[e] << endl;
cout << way[e].size() << endl;
for (int i = 0; i < way[e].size(); i++) cout << way[e][i] << ' ';

메인함수에서 다익스트라를 돌린뒤 dist[e]를 출력하고 (s에서 e까지의 비용)

way[e]를 출력한뒤 (e까지 가는 경로의 수)

way[e]안의 모든 숫자를 출력한다. (e까지 가는 경로)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int dist[1001];
int s, e;
vector<pair<int, int>> graph[1001];
vector<int> way[1001];

void dijkstra() {
	for (int i = 0; i < 1001; i++) dist[i] = 987654321;
	way[s].push_back(s);
	priority_queue<pair<int, int>> pq;
	dist[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (dist[now] < cost) continue;
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ -(cost + nextCost), next });
				way[next].clear();
				for (int j = 0; j < way[now].size(); j++) way[next].push_back(way[now][j]);
				way[next].push_back(next);
			}
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
	}
	cin >> s >> e;
	dijkstra();
	cout << dist[e] << endl;
	cout << way[e].size() << endl;
	for (int i = 0; i < way[e].size(); i++) cout << way[e][i] << ' ';
}

전체코드다.