190207 BOJ 1753번 최단경로

다익스트라 알고리즘

다익스트라를 사용해서 푸는 기본 문제.

D[i] : 출발점에서 i 까지 갈 때 최소 비용. 출발점을 제외하고 모두 아주 큰 값으로 초기화해준다.

예제 입력을 그림으로 나타냈다.

#include <iostream>
#include <vector>
#include <queue>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX 2147000000
#define pii pair<int, int>
using namespace std;
struct cmp { //비용이 적은 것부터 우선으로 뽑기.
    bool operator()(pii a, pii b) {
        return a.second > b.second;
    }
};
int D[20001];
int N, M, start, X, Y, W;
vector<pii> edge[20001];
priority_queue<pii, vector<pii>, cmp> q;
int main() {
    sws;
    cin >> N >> M;
    cin >> start;
    FOR(i, 0, N + 1) D[i] = MAX;
    while (M--) {
        cin >> X >> Y >> W;
        edge[X].push_back(mp(Y, W)); //목표 노드, 비용
    }
    D[start] = 0;
    q.push(mp(start, 0));
    while (!q.empty()) {
        int now = q.top().first;
        q.pop();
        for (pii next : edge[now]) {
            int nnode = next.first;
            int ncost = next.second;
            if (D[nnode] > D[now] + ncost) {
                D[nnode] = D[now] + ncost;
                q.push(mp(nnode, D[nnode]));
            }
        }
    }
    FOR(i, 1, N + 1) {
        if (D[i] == MAX) cout << "INF\n";
        else cout << D[i] << endl;
    }
}