본문 바로가기

BOJ

백준 1753 / 최단경로



다익스트라 문제.



가중치가 붙어있으면 BFS와 queue를 사용하여 풀 수 없다.


(음수인 가중치가 있다면 다익스트라도 사용할 수 없다.)



다익스트라에 대한 정보는 꺼무위키에서 보자.


https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



다익스트라를 구현하기 위해선 우선순위 큐(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(20001987654321);
    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<intint>>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