문제 출처

1. 문제설명

  • 방향 그래프와 시작점이 주어졌을 때, 다른 모든 정점으로의 최단 경로를 구하라
    • 시작점 자신은 0이다.
  • 문제 분류
    • Graph, Dijkstra


2. 알고리즘 설계

  • 간선과 가중치가 최대 10까지 주어지므로, 다익스트라로 풀이할 수 있겠다.
  • 다익스트라는 BFS와 굉장히 유사한데, 우선순위 큐(pq)를 사용한다는 특징이 있다.
    • 가중치가 적은 순으로 쌓여야 하므로…
  • 보통은 pq를 pair형으로 선언해서 가중치를 앞에 두고 풀이할 것이다.
    • 나는 인접행렬은 노드가 앞이고, pq는 가중치가 앞인 게 헷갈려서 커스텀 자료구조를 사용했다.
  • 이제 정점을 하나씩 꺼내면서 연결된 노드들을 pq에 담으면 된다.
    • 단, 다음 노드의 가중치가 현재 노드와 다음 노드 가중치의 합보다 작다면 넣는다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int INF = 987654321;
int V, E, K, u, v, w;
vector<pii> adj[20'002];
int vis[20'002];

// custom
struct comp {
    int v, w;
    comp(int _v, int _w) {v = _v, w = _w;}
    bool operator<(const comp &other) const {
        return w > other.w;
    }
};

void Dijkstra() {
    priority_queue<comp> pq;
    pq.push({K, 0});
    vis[K] = 0;

    while(!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

		// 연결된 정점들을 꺼내는데
        for(auto nxt : adj[cur.v])

			// 갱신할 가중치가 더 작을 때만 pq에 넣는다.
            if(vis[nxt.first] > cur.w + nxt.second) {
                pq.push({nxt.first, cur.w + nxt.second});
                vis[nxt.first] = cur.w + nxt.second;
            }
    }
}

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

    cin >> V >> E >> K;
    while(E--) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    fill(vis, vis+V+1, INF);  // 0~V번까지 INF로 초기화
    Dijkstra();

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

    return 0;
}