[백준 1753] 최단경로 (C++)

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

1753번: 최단경로

1. 주의할 점

- 다익스트라 문제지만, 2중 For문이 아닌 Heap형태의 우선순위 큐를 이용해야만 풀 수 있는 문제다.

- 다익스트라의 경우 다른 Node를 방문할때 Visit을 True로 바꾸는 것이 아닌, Priority_Queue에서 빼낼 때 True로 전환한다.

 

2. 구현

- 구조체를 적용한 우선순위큐를 작성한다. 우선순위큐의 적용기준은 가중치값이 낮은것이 우선적으로 나오도록 설정했다.

- 우선순위큐에서 Pop한 다음 Visit에 대한 조건을 처리하자 -> 아니면 계속 뺑뻉 돈다

 

#define MAX 987654321
#include <iostream>
#include <queue>
#include <vector>
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[20001];
int dist[20001];
bool visit[20001] = { false, };
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, start,s,e,val;
	cin >> node >> edge >> start;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
	}
	for (int i = 1; i <= node; i++)
		dist[i] = MAX;
	dist[start] = 0;
	priority_queue<info,vector<info>,cmp> pq;
	tmp.idx = start;
	tmp.val = 0;
	pq.push(tmp);
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		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 (visit[next]) continue;
			if (dist[next] > dist[cidx] + nv) {
				dist[next] = dist[cidx] + nv;
				tmp.idx = next;
				tmp.val = dist[next];
				pq.push(tmp);
			}
		}
	}
	for (int i = 1; i <= node; i++) {
		if (dist[i] == MAX) cout << "INF" << '\n';
		else cout << dist[i] << '\n';
	}
	system("pause");
	return 0;
}