백준 1753 - 최단 경로

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

문제 해설

가장 기본적이고 정형화된 다익스트라 문제이다!

다익스트라 알고리즘에서는 우선순위 큐를 사용하는데 기본적으로 우선순위 큐는 값이 큰 것부터 우선적으로 나가게 된다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int V, E;
int startPoint;
int dist[20002]; // dist[x] : 시작점으로부터 점 x까지의 최단 거리를 저장한다.
vector<vector<pair<int, int>>> graph;

void dijkstra(int start) {
    // 초기값은 무한대로 설정해 놓는다.
    for (int i = 1; i < V + 1; i++) {
        dist[i] = INF;
    }
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while (!pq.empty()) {
        int cntDist = -pq.top().first;
        int cntVertex = pq.top().second;
        pq.pop();

        // 현재 점까지의 거리와 저장된 최단거리를 비교한다.
        // 현재 점까지의 거리가 더 큰 경우는 나중에 최단거리가 갱신된 것이다.
        // 우리는 각 점에 최단거리로 간 상태에 대해서만 갱신을 진행하므로 밑의 연산은 진행하지 않는다.
        if (cntDist > dist[cntVertex]) {
            continue;
        }

        // 아래 로직을 대신 사용해도 결과는 똑같이 나온다.
        // 즉 현재 점까지의 거리가 최단거리까지와 일치하는지 확인하는 단계이다.
        // if (cntDist != dist[cntVertex]) {
        //     continue;
        // }

        for (int i = 0; i < graph[cntVertex].size(); i++) {
            int nextVertex = graph[cntVertex][i].first;
            int weight = graph[cntVertex][i].second;
            // cntDist 대신 dist[cntVertex]를 사용해도 결과는 동일하다
            // int nextDist = dist[cntVertex] + weight;
            int nextDist = cntDist + weight;


            if (dist[nextVertex] > nextDist) {
                dist[nextVertex] = nextDist;
                // 값을 음수로 저장해 우선순위가 반대가 되도록 한다.
                pq.push({-nextDist, nextVertex});
            }
        }
    }
}

int main(void) {
    cin >> V >> E;
    cin >> startPoint;

    graph = vector<vector<pair<int, int>>>(V + 1);
    for (int i = 0; i < E; i++) {
        int a, b, weight;
        cin >> a >> b >> weight;
        graph[a].push_back({b, weight});
    }

    dijkstra(startPoint);

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

    return 0;
}

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 우선순위 큐에 greater<pair<int, int>>> pq 정렬 방식을 통해 값이 작은 것부터 우선적으로 나가게 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 2000000000

// 정점의 개수 : v, 간선의 개수 : e
int v, e;
vector<vector<pair<int, int>>> graph;
vector<int> dist;
vector<bool> check;
int start_node;

void dijkstra()
{
    for (int i = 1; i <= v; i++)
        dist[i] = INF;
    dist[start_node] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start_node});

    while (!pq.empty())
    {
        int weight = pq.top().first;
        int cnt_node = pq.top().second;
        pq.pop();

        if (check[cnt_node] == true)
            continue;
        check[cnt_node] = true;

        // 점 cnt_node에 연결된 간선의 개수
        int edge_num = graph[cnt_node].size();
        for (int j = 0; j < edge_num; j++)
        {
            // from : 현재 위치, to : 다음 위치, from_to_weight : 현재위치에서 다음위치 까지의 가중치
            int from = cnt_node,
                to = graph[cnt_node][j].first,
                from_to_weight = graph[cnt_node][j].second;

            if (dist[to] > dist[from] + from_to_weight)
            {
                dist[to] = dist[from] + from_to_weight;
                pq.push({dist[to], to});
            }
        }
    }
}

int main(void)
{
    scanf("%d %d %d", &v, &e, &start_node);
    dist = vector<int>(v + 1, INF);
    check = vector<bool>(v + 1, false);
    graph = vector<vector<pair<int, int>>>(v + 1);

    for (int i = 0; i < e; i++)
    {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);
        graph[from].push_back({to, weight});
    }
    dijkstra();

    for (int i = 1; i <= v; i++)
    {
        if (dist[i] == INF)
            printf("INF\n");
        else
        {
            printf("%d\n", dist[i]);
        }
    }

    return 0;
}