백준 11779 최소비용 구하기 2

문제링크

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

문제

풀이

기본적인 다익스트라 + 경로찾기 문제

1. 비용은 우선순위큐를 이용한 다익스트라 알고리즘으로 구해주었다.
2. 경로찾기는 int route[1001] 배열을 두어 다익스트라 알고리즘에서 dist 갱신시 route 배열에 해당 정점이 어떤 정점으로 부터 왔는지에 대한 기록도 갱신 해주었다.
3. 이후에는 dfs를 이용하여 route 배열에 대해 도착지에서 시작해 따라들어가며 출발지점의 까지의 경로를 route_ans 벡터에 넣어주었다.
4. route_ans 벡터의 back부터 출력해주면 경로가 출력된다.

코드

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

int n, m, from, to;
vector<int> route_ans;
vector<pair<int, int>> v[1001];
priority_queue<pair<int, int>> pq;
int dist[1001];
int route[1001];

void dijkstra(int start) {
	fill(dist, dist + n + 1, INF);
	dist[start] = 0;
	pq.push({ 0,start });

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

		for (int i = 0; i < v[now].size(); i++) {
			int ncost = v[now][i].first + cost;
			int next = v[now][i].second;
			if (ncost < dist[next]) {
				dist[next] = ncost;
				route[next] = now;
				pq.push({ -ncost,next });
			}
		}
	}
}

void trace_route(int now){
	if (now == 0) return;
	
	route_ans.push_back(now);
	trace_route(route[now]);

}

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

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ c,b });
	}
	cin >> from >> to;
	dijkstra(from);
	trace_route(to);
	cout << dist[to] << '\n';
	cout << route_ans.size() << '\n';

	int sz = route_ans.size();
	for (int i = 0; i < sz; i++) {
		cout << route_ans.back() << ' ';
		route_ans.pop_back();
	}
}

후기

익숙한 유형의 문제라 쉽게 풀었다.
이제보니까 자꾸 풀던 유형의 문제만 푸는것 같다.
안풀어본 유형의 문제도 풀어보자.