[백준/C++] 1753번: 최단경로

Problem

---

Solution

---

변수 및 데이터 입력**: `n`, `m`, `k`를 입력받는다. `INF`라는 상수를 사용하여 무한을 나타낸다. `INT_MAX`는 C++에서 정수의 최댓값을 나타내는 상수이다. `graph`는 정점과 간선 정보를 저장하는 2차원 벡터이고 `distance`는 각 정점까지의 최단 거리를 저장하는 배열로 초기값은 모두 무한으로 설정한다. `m`번 만큼 간선 정보를 입력받아 `graph`에 저장하고 각 간선은 시작 노드, 도착 노드, 비용으로 구성한다. `dijkstra` 함수를 정의한다. 우선순위 큐 `q`를 사용하여 노드까지의 최단 거리를 기준으로 노드를 선택하고 알고리즘을 통해 시작 노드로부터 각 노드까지의 최단 거리를 계산하고 `distance` 배열에 저장한다. `dijkstra` 함수를 호출하여 시작 노드 `k`로부터 모든 노드까지의 최단 거리를 계산하고 각 노드까지의 최단 거리를 출력한다. 만약 해당 노드까지의 거리가 무한대인 경우 "INF"를 출력하고 아닌 경우에는 실제 최단 거리를 출력한다.

Answer

---

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    int k;
    cin >> k;

    const int INF = INT_MAX;

    vector<vector<pair<int, int>>> graph(n + 1);
    vector<int> distance(n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }

    auto dijkstra = [&graph, &distance](int start) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push(make_pair(0, start));
        distance[start] = 0;

        while (!q.empty()) {
            int dist = q.top().first;
            int now = q.top().second;
            q.pop();

            if (distance[now] < dist) {
                continue;
            }

            for (const auto& edge : graph[now]) {
                int cost = dist + edge.second;
                if (cost < distance[edge.first]) {
                    distance[edge.first] = cost;
                    q.push(make_pair(cost, edge.first));
                }
            }
        }
    };

    dijkstra(k);

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

    return 0;
}

https://www.acmicpc.net/problem/1753