백준 11779번 최소비용 구하기 2

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/11779

 

 

11779번: 최소비용 구하기 2

 

 

이번 문제는 다익스트라(Dijkstra) 문제였습니다. 

 

최단 경로뿐만 아니라 최단 경로에 포함된 정점들까지 출력해야 하는 문제였습니다.

 

 

 

 

《문제 풀이》

 

1. 입력한 출발 도시에서 도착 도시까지의 경로는 단방향이므로 단방향 연결

2. 다익스트라 (최단 경로 구하기)

     (1) 출발 도시를 큐에 삽입

     (2) 출발 도시를 제외한 모든 도시의 거리는 INF (출발 도시는 0)

     (3) 현재 도시와 연결되어 있는 도시의 거리가 현재 도시의 거리 + 버스 비용 보다 크다면

          (1) 다음 도시의 거리를 현재 도시의 거리 + 버스 비용으로 갱신

          (2) 다음 도시를 큐에 삽입

          (3) 경로 배열에 이전 도시를 기록 ⭐ (경로에 포함된 도시를 구하기 위함) 

3. 도착 도시부터 출발 도시까지의 경로를 route 벡터에 삽입

4. route 벡터의 사이즈가 경로에 포함된 도시의 개수가 됨 (원소들은 도시)

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 1001
#define INF 987654321

using namespace std;

int n, m;
int dist[MAX];
int path[MAX]; // 경로 추적을 위한 배열  
vector<pair<int, int>> v[MAX];

void dijkstra(int from) {
	queue<int> q;
	q.push(from);
	for(int i=1; i<=n; i++) 
		dist[i] = INF;
		
	dist[from] = 0; // 출발 도시 
	
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		
		for(int i=0; i<v[node].size(); i++) {
			int nxtNode = v[node][i].first;
			int cost = v[node][i].second;
			
			if(dist[node] + cost >= dist[nxtNode])
				continue;
			
			dist[nxtNode] = dist[node] + cost;
			q.push(nxtNode);
			path[nxtNode] = node; // 이전 도시 기록  
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
		
	cin>>n>>m;
	
	for(int i=0; i<m; i++) {
		int from, to, cost;
		cin>>from>>to>>cost;
		
		// 단방향 연결  
		v[from].push_back({ to, cost });
	}
	
	int from, to;
	cin>>from>>to;
	
	dijkstra(from);  
	
	// 최소 비용  
	cout<<dist[to]<<"\n";
	
	vector<int> route;
	int idx = to;
	while(idx) {
		route.push_back(idx);
		idx = path[idx];
	}
	
	// 경로에 포함된 도시 개수  
	cout<<route.size()<<"\n";
	reverse(route.begin(), route.end());
	
	for(int i=0; i<route.size(); i++)
		cout<<route[i]<<" "; // 도시  
		
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면