[ BOJ 백준 1753번 - 최단경로 ] 해설 및 코드

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

 

목적

방향그래프에서 최단경로를 구하자.

 

접근법

1. 최단거리를 구하는데 다익스트라 알고리즘을 이용한다.

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX_V 20001
#define MAX_W 200001
using namespace std;
 
struct info {
    int u, w;
    bool operator<(const info& oth) const { return w > oth.w; }
};
 
void go(int V, int K, vector<info>* G) {
    vector<int> sp(V + 1, MAX_W); sp[K] = 0;
    priority_queue<info> pq; pq.push({ K,0 });
    while (!pq.empty()) {
        int w = pq.top().w, u = pq.top().u; pq.pop();
        if (sp[u] != w)continue;
        for (auto& e : G[u]) {
            int tmp = w + e.w;
            if (sp[e.u] > tmp) {
                sp[e.u] = tmp;
                pq.push({ e.u,tmp });
            }
        }
    }
 
    for (int i = 1; i <= V; ++i) {
        if (sp[i] == MAX_W)cout << "INF\n";
        else cout << sp[i] << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int V, E, K; cin >> V >> E >> K;
    vector<info> G[MAX_V];
    while (E--) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({ v,w });
    }
    go(V, K, G);
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.