[백준 1916] 최소비용 구하기 (C++)

문제 링크: https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

1. 주의할 점

- 다익스트라를 통해 구현가능하다.

- 우선순위큐를 사용하여 이미 현 위치의 Node에서 출발한 적이 있는 경우, 이후에 같은 Node에서 출발하려는 값들은 무시한다.

- Dist 배열을 통해 출발점 -> 다른 Node들까지의 최소거리를 구한다

 

2. 구현

- 가중치의 값이 작은것이 우선순위큐의 Top에 오도록 Cmp를 설정한다

- Node +1만큼의 리스트를 만든다

- 다음 Node로 이동하려고 할때, 지금까지 자신이 이동한 거리 + 다음 Node까지의 거리가 이미 Dist배열에 저장된 값보다 작은 경우 다음 Node로 갈 수 있도록 설정한다

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
vector<info> v[1001];
int dist[1001];
bool visit[1001] = { false, };
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, s, e, val, start, dest;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
	}
	cin >> start >> dest;
	for (int i = 1; i <= node; i++)
		dist[i] = MAX;
	priority_queue<info, vector<info>, cmp> pq;
	tmp.idx = start;
	tmp.val = 0;
	pq.push(tmp);
	long long result;

	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		if (cidx == dest) {
			result = cv;
			break;
		}
		if (visit[cidx]) continue;
		visit[cidx] = true;
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			int nv = v[cidx][i].val;
			if (dist[next] > cv + nv) {
				dist[next] = cv + nv;
				tmp.idx = next;
				tmp.val = cv + nv;
				pq.push(tmp);
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}