다익스트라 문제.
가중치가 붙어있으면 BFS와 queue를 사용하여 풀 수 없다.
(음수인 가중치가 있다면 다익스트라도 사용할 수 없다.)
다익스트라에 대한 정보는 꺼무위키에서 보자.
다익스트라를 구현하기 위해선 우선순위 큐(priority_queue)를 사용해야 한다.
일반 queue / BFS 사용법과 다익스트라/우선순위 큐의 사용법 차이는 다음과 같다.
1. 우선순위 큐에서 pair를 사용할 시 first로 비교하기 때문에 가중치를 first에 넣어주어야한다. (first가 같을 시 second를 비교한다)
2. pair에 가중치를 넣어줄 때 -를 붙여서 넣어주어야한다. pop할떄도 -를 붙여야한다. (중요)
여기서 -로 넣는 이유?
priority_queue STL은 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성
따라서 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하기 위함
출처: https://www.crocus.co.kr/546 [Crocus]
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<stdio.h> #include<iostream> #include<vector> #include<queue> using namespace std; int main() { //freopen("Text.txt", "r", stdin); int v, e; int start; cin >> v >> e; cin >> start; vector<int> dist(20001, 987654321); vector<vector<pair<int,int>>>arr; arr.resize(v + 1); for (int i = 0; i < e; i++) { int from, to, c; scanf("%d %d %d", &from, &to, &c); arr[from].push_back(make_pair(to, c)); } priority_queue<pair<int, int>>pq; pq.push(make_pair(0, start)); dist[start] = 0; while (!pq.empty()) { int d = -pq.top().first; int now = pq.top().second; pq.pop(); if (dist[now] < d)continue; for (int i = 0; i < arr[now].size(); i++) { int to = arr[now][i].first; int cost = arr[now][i].second; if (dist[to] > cost + d) { dist[to] = cost + d; pq.push(make_pair(-(cost+d), to)); } } } for (int i = 1; i <= v; i++) { if (dist[i]==987654321) { printf("INF\n"); } else { printf("%d\n", dist[i]); } } } | cs |
'BOJ' 카테고리의 다른 글
백준 1107 / 리모컨 (0) | 2019.01.17 |
---|---|
백준 5719 / 거의 최단 경로 (0) | 2019.01.17 |
백준 9205 / 맥주 마시면서 걸어가기 (0) | 2019.01.11 |
백준 11559 / Puyo Puyo (0) | 2019.01.11 |
백준 1726 / 로봇 (0) | 2019.01.10 |