1753번 - 최단경로

📌문제

👉 문제보기

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 9999999
#define MAX_SIZE 20005

using namespace std;

int n, e, k;
vector<vector<pair<int, int>>> vec(MAX_SIZE);

vector<int> dijkstra(int start) {
    vector<int> path(n + 1, INF);
    path[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;	// 힙

    pq.push(make_pair(0, start)); // 가중치와 번호

    while (!pq.empty()) {
        int distance = pq.top().first;
        int current = pq.top().second;

        pq.pop();

        if (distance > path[current]) continue; // 최단 거리 아닌 경우
        for (int i = 0; i < vec[current].size(); i++) {
            int next = vec[current][i].first;
            int nextDist = vec[current][i].second + distance;

            if (nextDist < path[next]) {
                path[next] = nextDist;
                pq.push(make_pair(nextDist, next));
            }
        }
    }

    return path;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> e >> k;

    int u, v, w;
    for (int i = 0; i < e; i++) {
        cin >> u >> v >> w;
        
        vec[u].push_back(make_pair(v, w));
    }

    vector<int> path = dijkstra(k);


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

    return 0;
}

🍳문제 풀이

2차원 배열을 사용하지 않고 힙을 사용해야 하는 다익스트라 문제 O(NlogN)

다익스트라 : 하나의 정점에서 다른 모든 정점까지의 최단 경로

2차원 배열을 사용하면 간선의 개수가 20000개까지있으므로 20000 * 20000 = 400000000 시간 초과 O(N^2)
시작점 k로부터 다른 점까지의 최소 거리를 모두 출력하는 문제이다.

1. 시작 노드 거리는 0
2. 현재 노드의 거리가 저장된 거리보다 긴 경우 continue
3. 현재 노드에서 이동할 수 있는 다음 노드의 거리가 저장된 다음 노드 거리보다 짧으면 저장하고 pq에 넣기

처음에 시간 초과가 나서 백준 질문텝을 읽어봤다. c++ 라이브러리의 우선순위큐는 first 순으로 정렬이 되는 것이 중요한 포인트. 거리가 짧은 순으로 우선순위큐에 들어가야하는데 first를 노드 번호로 해버리면 다익스트라의 의미가 사라지는 것
make_pair(거리, 노드번호) 여야 제대로 출력할 수 있다.