[백준 BOJ 1916] 최소비용 구하기

백준 링크

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

풀이

• 우선순위 큐(힙)을 사용한 다익스트라를 이용해 O(ElogV)로 풀 수 있었다
• 다익스트라:
  • Dist[i] : 시작부터 i까지의 최단거리
  • Check[i] : I 방문했으면 true
  • 1. Check[i] = false 인 I 중 dist 가장 작은 노드 선택(노드 V) => 우선 순위큐로 시간 단축
  • 2. V와 연결된 모든 간선(from, to, cost) 검사, dist[to] > dist[from]+cost 이면 dist[to] 갱신
  • 3. 1,2 반복
  • 참고https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

코드

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

struct Edge {
	int to, cost;
};
vector<vector<Edge>> edge(1005);
int n, m, s, e, dist[1005];
bool c[1005];

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	dist[s] = 0;
	pq.push(make_pair(0, s));
	while(!pq.empty()) {
		pair<int,int> cur = pq.top();
		pq.pop();
		int size = edge[cur.second].size(), from = cur.second;
		if (c[from]) continue;
		c[from] = true;
		for (int j = 0; j < size; j++) {
			int to = edge[from][j].to, cost = edge[from][j].cost;
			if (dist[to] > dist[from] + cost)
				dist[to] = dist[from] + cost;
			pq.push(make_pair(-dist[to], to));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dist[i] = 987654321;
	}
	int cost;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> cost;
		edge[s].push_back({ e, cost });
	}
	cin >> s >> e;
	dijkstra();
	cout << dist[e];
}