[C++]백준 11779번 : 최소비용 구하기

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

기본적인 다익스트라 알고리즘 적용 문제

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 거리를 구하는데 사용된다.

우선순위 큐를 사용하여 거리를 가중치로 두고 구현하면 시간복잡도 O(|E|log|V|)를 가진다.

 

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

struct comp{
	bool operator()(pair<int, int> a, pair<int, int> b){
		return a.second > b.second;
	}
};

int N, M, s, d, c;
vector<vector<pair<int, int>>> e;
int dp[1001];
vector<int> route[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	e.resize(N + 1);
	for (int i = 1; i <= N; i++)
		dp[i] = 987654321;
	
	for (int i = 0; i < M; i++){
		cin >> s >> d >> c;
		e[s].push_back({ d, c });
	}
	cin >> s >> d; // src, dest

	dp[s] = 0;
	pq.push({ s, 0 });

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

		if (dp[src] < cost)
			continue;

		for (int i = 0; i < e[src].size(); i++){
			int dest = e[src][i].first, ccost = dp[src] + e[src][i].second;

			if (dp[dest] > ccost){
				pq.push({ dest, ccost });
				dp[dest] = ccost;
                
                // 경로 갱신
				route[dest].clear();
				for (int j = 0; j < route[src].size(); j++)
					route[dest].push_back(route[src][j]);
				route[dest].push_back(src);
			}
		}
	}
	
    // route[i]는 i 이전까지의 경로
	route[d].push_back(d);
	cout << dp[d] << "\n" << route[d].size() << "\n";
	for (int i = 0; i < route[d].size(); i++)
		cout << route[d][i] << " ";

	return 0;
}