[백준 1753] 최단경로 (C++)

문제 출처 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[20001];
vector<vector<pair<int, int>>> v(20001);
 
void dijk(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dis[i] = 1000000000;
    }
    cin >> s;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    dijk(s);
    for (int i = 1; i <= n; i++) {
        if (dis[i] != 1000000000) cout << dis[i] << endl;
        else cout << "INF" << endl;
    }
    return 0;
}

 

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 정점의 개수 만큼 가중치배열을 선언하고 무한(10억)값을 넣어준다.

시작점 번호를 입력 받는다.

시작 정점 번호, 도착 정점 번호, 가중치를 입력 받아 v[시작 정점 번호]에 pair(도착 정점 번호, 가중치)을 넣어준다.

dijk(시작점) 함수를 돌린 후 n개의 정점을 돌며 무한(10억)값이 아니라면 해당 값을, 무한값이라면 INF를 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (가중치 오름차순으로 정렬)
start에서 start까지의 가중치는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 가중치는 now까지의 가중치와 now에서 해당 노드로 가는 가중치의 합이다.
만약 방금 구한 값이 가중치배열에 있는 값보다 작다면 최단경로이므로 업데이트 하고 큐에 넣어준다.