[백준/알고리즘] 1916번 최소비용 구하기 (골드 5)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1916번

 

N개의 도시가 있고, 도시 사이를 이동하는 버스 M개가 있다. 도시 A에서 도시 B로 가는 버스 비용을 최소화 하려고 한다. 최소 비용을 출력하시오.

 

풀이 알고리즘 : 다익스트라 알고리즘

 

한 정점에서 다른 정점으로 이동하는 최소 거리를 구하는 문제입니다.도시 A에서 다른 모든 정점으로의 최소 거리를 구하기 위해 다익스트라 알고리즘을 이용하여 구현하였습니다.

 

모든 도시를 이중 for문으로 탐색하여 구하는 방법이 있고,우선순위 큐를 이용하여 구하는 방법이 있는데, 후자가 보통 빠르기에 우선순위 큐를 이용하여 구현하겠습니다.

 

우선순위큐에 <A에서의 거리, 현재 노드 번호>를 입력하였고, 거리가 가까운 정점을 우선순위로 탐색하고,해당 정점에서 또 확인하지 않고 연결되어 있는 정점으로의 최소 거리를 갱신하여 PQ에 다시 입력하는 것을 반복해줍니다.

 

그러면 모든 정점이 방문되고, while문을 탈출하게 되면, 갱신되어 있는 최소 거리에서 도시 B로의 거리를 출력하면 됩니다.

 

다음은 정답코드입니다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, stt, dest;
	vector< map<int, int> > adj(1000 + 1);
	vector<int> dist(1000 + 1, 100000000);
	vector<bool> check(1000 + 1, false);
	priority_queue< pii, vector<pii>, greater<pii> > pq;

	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int s, d, v;
		cin >> s >> d >> v;
		pair<map<int, int>::iterator, bool> pib = adj[s].insert(mp(d, v));
		if(!pib.second) {
			adj[s][d] = min(adj[s][d], v);
		}
	}
	cin >> stt >> dest;

	dist[stt] = 0;
	pq.push(mp(0, stt));

	while(!pq.empty()) {
		int cur_dest = pq.top().second;
		int cur_val = pq.top().first;

		pq.pop();

		if(!check[cur_dest]) {
			check[cur_dest] = true;
		} else {
			continue;
		}

		for(auto i = adj[cur_dest].begin(); i != adj[cur_dest].end(); i++) {
			int next_dest = i->first;
			int next_val = i->second;
			if(cur_val + next_val < dist[next_dest]) {
				dist[next_dest] = cur_val + next_val;
				pq.push(mp(dist[next_dest], next_dest));
			}
		}
	}

	cout << dist[dest];

	return 0;
}