https://codeforces.com/contest/20/problem/C
Problem - C - Codeforces
codeforces.com
// 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에 관한 포스팅이 필요함.


'Algorithm Study > c++' 카테고리의 다른 글
| [C++] Dijkstra Algorithm / codeforces-449-B (1) | 2023.06.13 |
|---|---|
| [C++] codeforces-707-B (1) | 2023.06.10 |
| [C++] DFS / codeforces-217-A (1) | 2023.06.10 |
| [C++] DFS(Depth-First Search) vs BFS(Breath-First Search) (1) | 2023.06.10 |
| [C++] queue 사용 & 예제 (0) | 2023.06.09 |