[C++] Dijkstra(다익스트라 알고리즘) / codeforces-20-C

https://codeforces.com/contest/20/problem/C

Problem - C - Codeforces

 

// codeforces 20 C - Dijkstra?
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
vector<pair<int, int>> Edges[100005];
long long visit[100005];
long long L[100005];
int pre[100005];
int wei[100005];
int ans[100005];
int ansL;
 
class pkt {
public:
	long long l;
	int w, a, b;
	// sort할 때, 무엇을 기준으로 할지 오버로딩 해주는 부분. 반드시 const 활용
	bool operator<(const pkt& k) const {
		// l을 기준으로 내림차순으로 정렬. 큰 것 -> 작은 것
		return l > k.l;
	}
};
 
// 우선 순위 : l이 작은것 ~> node가 작은 것
priority_queue<pkt>Q;
 
void dijkstra(int s) {
	pkt p, q;
	p.l = 0;
	p.w = 0;
	p.a = 0;
	p.b = s;
 
	Q.push(p);
	while (!Q.empty()) {
		p = Q.top();
		//cout << "* 노드 [ " << p.b << " ] 꺼냈다." << endl;
		Q.pop();
		if (visit[p.b]) {
			//cout << "** 노드 [ " << p.b << " ]는 이미 방문했다" << endl;
			continue;
		}
		visit[p.b] = true;
		L[p.b] = p.l;
		pre[p.b] = p.a;
		wei[p.b] = p.w;
		for (int i = 0; i < Edges[p.b].size(); i++) {
			q.l = L[p.b] + Edges[p.b][i].second;
			q.w = Edges[p.b][i].second;
			q.a = p.b;
			q.b = Edges[p.b][i].first;
			Q.push(q);
			//cout << "방금 노드 [ " << q.b << " ] 큐에 들어갔다 (끝)" << " --- l은 : "<< q.l << "  현재 Q에는 : " << Q.size() << endl;
		}
	}
}
 
int main()
{
	int n, m, r, s, w;
	int i, j;
	pkt p, q;
 
	cin >> n >> m;
 
	for (int i = 1; i <= m; i++) {
		cin >> r >> s >> w;
 
		Edges[r].push_back(make_pair(s, w));
		Edges[s].push_back(make_pair(r, w));
	}
 
	for (i = 1; i <= n; i++) L[i] = (int)1E12;
	dijkstra(1);
	if (L[n] == (int)1E12) { printf("-1\n"); return 0; }
	i = 1;
	ans[1] = n;
 
	/*
	cout << "pre의 배열 안에는 : ";
	for (i = 1; i <= n; i++) {
		cout << pre[i] << " ";
	}
	cout << endl;
	*/
 
	i = 1;
	while (ans[i] != 1)
	{
		i++;
		ans[i] = pre[ans[i - 1]];
	}
	while (i > 1) {
		printf("%d ", ans[i]);
		i--;
	}
 
	printf("%d\n", ans[1]);
 
	return 0;
}

pkt로 구성된 우선순위 큐(Q)는 'l이 작은것, l이 같다면 q.b가 작은 것' 의 우선순위를 따른다. C++ 에서 연산자 오버로딩을 통한 정렬은 처음 봤다. 이해하는데 시간을 조금 오래썼다. bool operator에 관한 포스팅이 필요함.

이해가 잘 안돼서 초반 case는 직접 작성함