[BOJ 1916 // C++] 최소비용 구하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1916번 문제인 최소비용 구하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

이번 문제는 다익스트라(Dijkstra) 알고리즘을 이용해 출발지점에서 도착지점까지 가는 데에 드는최소 비용을 구하는 문제이다.

다익스트라 알고리즘 코딩을 연습하기 위해 이 문제를 골라보았다.

 

다익스트라 알고리즘으로 그래프를 탐색해나가다가, 도착점과 마주치면 그 즉시 반복문을 탈출하고 도착점까지의 거리를 출력해주면 되는 문제이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::vector;
using std::pair;
using std::priority_queue;

vector<pair<int, int>> graph[1001];
priority_queue<pair<int, int>> pq;
int distance[1001];
bool done[1001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 0;i < M;i++) {
        int S, E, W;
        cin >> S >> E >> W;
        graph[S].push_back({ E,W });
    }
    int S, E;
    cin >> S >> E;
    for (int i = 1;i <= N;i++) {
        distance[i] = 100000001;
    }
    distance[S] = 0;
    pq.push({ 0,S });
    while (!pq.empty()) {
        int current = pq.top().second; pq.pop();
        if (done[current]) continue;
        else if (current == E) break;
        done[current] = true;
        for (auto u : graph[current]) {
            int f = u.first, s = u.second;
            if (distance[f] > distance[current] + s) {
                distance[f] = distance[current] + s;
                pq.push({ -distance[f],f });
            }
        }
    }
    cout << distance[E];

    return 0;
}