백준 1753 최단경로

작성일 | In |

Problem : 최단경로

유형 : 다익스트라

문제 해석

  • 한 점에서 다른 모든 정점으로의 최단 경로를 구하라.

문제 재해석

  • 한 점으로부터의 다른 점들 간의 최단 경로를 찾는 문제이다.

해결 전략

  • 정점이 2만 간선이 30만이다.
  • 간선이 많으므로 Dijkstra로 해결한다.

구현, 설계

  • 다익스트라를 구현한다.
  • { 비용, 다음 정점 } 으로 pair를 만든다.
  • 처음 node를 세팅할 때 pair의 순서에 주의 한다.

주의할 점

  • 서로 다른두 정점 사이에 여러개의 간선이 존재 할 수 있다.
  • heap을 이용하연, 어차피 최선의 선택을 하게 되므로 이 조건에 대한 처리가 동시에 된다.

디버깅

  • input 파일을 이상한것을 두고 output이 이상하다고 고민했다.
  • pq 를 선언할떄, greater 인자를 잘못된 것으로 설정 하였었다.

코드

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int INF = INT_MAX;
int n, m;
int st;

vector<pii> node[20002];
int cost[20002];

priority_queue<pii, vector<pii>, greater<pii> > pq;

void Print_Answer() {
    for (int i = 1; i <= n; ++i) {
        if (cost[i] == INF) cout << "INF\n";
        else cout << cost[i] << "\n";
    }
}

void Dijkstra() {
    pq.push({ 0, st });
    cost[st] = 0;
    
    while (!pq.empty()) {
        auto cur = pq.top();    pq.pop();
        int cur_cost = cur.first;
        int cur_spot = cur.second;

        if (cur_cost != cost[cur_spot]) continue;

        for (const auto nxt : node[cur_spot]) {
            int nxt_cost = cur_cost + nxt.first;
            int nxt_spot = nxt.second;

            if (nxt_cost < cost[nxt_spot]) {
                cost[nxt_spot] = nxt_cost;
                pq.push({ nxt_cost, nxt_spot });
            }
        }
    }
}


void Solve() {
    Dijkstra();
    Print_Answer();
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        cost[i] = INF;
    }
}
void Input() {
    cin >> n >> m;
    cin >> st;

    Init();

    int u, v, _cost;
    while (m--) {
        cin >> u >> v >> _cost;
        node[u].push_back({ _cost,v });
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 다익을 구현할때, 실수없이 물 흐르듯이 구현 할 수 있도록 연습하자.
  • 마치 BFS 구현 하는것 처럼.