[백준] 11779-최소비용 구하기2(C++) / 최신 통과 코드

문제링크: https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

다익스트라 문제이고, 추가 사항은 최소 경로를 구해야 하는 것이었습니다.

다익스트라는 일반적인 우선순위 큐 방식을 사용하였고, 경로를 저장하기 위해서는 자신의 출발지 값을 저장하게끔 구성을 해주었습니다.

 

접근방식

 

1. 일반적인 다익스트라 방식을 생각함

2. 최소 경로를 구하기 위해서 배열을 생성하고 출력

 

 

문제풀이 

 

1. 일반적인 다익스트라 구현

2. 최소 경로를 구하기 위해서 배열을 생성함

해당배열에는 자신의 부모정점을 저장함.

ex) 1->3이면 arr[3] = 1 

3. 해당 배열에서 while문을 사용하여 결과를 도출함 

일부 예외처리를 신경써주어야 했음.

아래 처럼 탐색할 필요없는 정점이라면 가지치기를 해주어야 통과할 수 있는 문제.

		if (cost > dist[cur])
			continue;

 

가지치기를 해주어야 하는점이 꽤나 까다로운 문제였습니다.

정답코드입니다.

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

int cnt = 0;


int dist[1001];
int before_val[1001] = { 0, };
vector <pair<int, int>> vec[1001];
int n, m, s, e; // 도시 개수, 버스의 개수, 출발지, 도착지 

void dijkstra() {

	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, s));
	dist[s] = 0; 
	while (!pq.empty()) {

		int cost = - pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		if (cost > dist[cur])
			continue;

		for (int i = 0; i < vec[cur].size(); i++) {
			int ncost = vec[cur][i].second;
			int ncur = vec[cur][i].first;

		
			if (dist[ncur] > cost + ncost) {
				dist[ncur] = ncost + cost;
				pq.push(make_pair(-dist[ncur], ncur));
				before_val[ncur] = cur;
			}
		}



	}

}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		dist[i] = 2000000000;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
	}

	cin >> s >> e;
	dijkstra();

	vector <int> arr;
	arr.push_back(e);
	int val = before_val[e];
	while (val) {
		arr.push_back(val);
		val = before_val[val];
	}
	

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

	return 0;
}