[ BOJ 백준 1916번 - 최소비용 구하기 ] 해설 및 코드

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

 

 

목적

두 정점간의 최단 거리를 구하자.

 

접근법

1. 다익스트라 알고리즘을 이용하여 정점간 최단 거리를 갱신해 나가다가 목적지를 만나면 출력 후 종료한다.

 

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX_N 1001
#define MAX_W (int)1e10
using namespace std;
 
struct info {
    int v, w;
    bool operator<(const info& oth) const { return w > oth.w; }
};
 
void go(int n,int a, int b, vector<info>* g) {
    vector<int> sp(n + 1, MAX_W); sp[a] = 0;
    priority_queue<info> pq; pq.push({ a,0 });
    while (!pq.empty()) {
        int w = pq.top().w, u = pq.top().v; pq.pop();
        if (sp[u] != w)continue;
        if (u == b) {
            cout << w;
            return;
        }
        for (auto& e : g[u]) {
            int tmp = w + e.w;
            if (sp[e.v] > tmp) {
                sp[e.v] = tmp;
                pq.push({ e.v,tmp });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<info> g[MAX_N];
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({ b,c });
    }
    int a, b; cin >> a >> b;
    go(n, a, b, g);
}

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

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