[백준] 1753 최단경로 / 다익스트라 알고리즘 / C++ 풀이

문제 링크

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

1753번: 최단경로

풀이 전략

'시작점에서 다른 모든 정점으로의 최단 경로'를 구하라고 한다. 다익스트라 알고리즘을 사용하면 특정 시작 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 따라서 다익스트라 알고리즘으로 접근한다.

 

C++ 풀이

/*
https://www.acmicpc.net/problem/1753
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>
#define INF (INT_MAX - 5000)
using namespace std;
void Solve();
typedef pair<int, int> weight_dst;
int V, E, K;
vector<vector<weight_dst>> A; /*Adjacent list*/
vector<bool> visit;
vector<int> dist;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();
}

void Solve() {
    cin >> V >> E;
    A.clear();
    visit.resize(V + 1);
    dist.resize(V + 1);
    fill(visit.begin(), visit.end(), false);
    fill(dist.begin(), dist.end(), INF);
    A.resize(V + 1);

    cin >> K; /*시작 정점의 번호*/
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        A[u].push_back(weight_dst{ w,v });
    }

    /*Dijkstra*/
    priority_queue<weight_dst, vector<weight_dst>, greater<>> pq;
    pq.push({ 0, K });
    dist[K] = 0;
    while (!pq.empty()) {
        weight_dst cur = pq.top();
        pq.pop();
        if (visit[cur.second]) {
            continue;
        }

        visit[cur.second] = true;
        dist[cur.second] = min(dist[cur.second], cur.first);

        for (const auto& next : A[cur.second]) {
            if (!visit[next.second]) {
                pq.push({next.first + dist[cur.second], next.second});
            }
        }

    }

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

 

다익스트라 구현 시 기억할 점

• 방문 배열 및 최단 거리 배열 갱신은 우선 순위 큐에서 빼면서 갱신한다.
• 동일한 도착 노드에 대해 최단 경로인 것이 우선 순위 큐에서 빼낼 때 선택된다.
• 아직 방문하지 않은 노드만 우선 순위 큐에 삽입한다. 
• {(현재 노드 + 다음 노드로의 거리), 다음 노드의 번호} 꼴로 삽입하면 된다.