문제 푼 날짜 : 2021-07-04

문제

문제 링크 : https://www.acmicpc.net/problem/1916

접근 및 풀이

최단경로 문제 중 다익스트라 알고리즘을 이용하여 풀 수 있는 기본적인 문제이다.
1753번 [최단경로] 문제와 동일하게 구현하였고, 문제에서 주어진 출발 도시(코드 내의 start 변수)에서 다른 도시까지의 최단거리를 구한 다음 도착 도시(코드 내의 end 변수)까지의 최단 거리 값을 출력해주었다.

코드

// 백준 1916번 : 최소비용 구하기
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 987654321

int dist[1001];
vector<pair<int, int>> bus[1001];

void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int vertex = pq.top().second;
        pq.pop();

        if (dist[vertex] < cost) {
            continue;
        }
        for (int i = 0; i < bus[vertex].size(); i++) {
            int next = bus[vertex][i].first;
            int nextDistance = cost + bus[vertex][i].second;

            if (dist[next] > nextDistance) {
                dist[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
    }

    while (M--) {
        int s, e, w;
        cin >> s >> e >> w;
        bus[s].push_back(make_pair(e, w));
    }
    int start, end;
    cin >> start >> end;

    dijkstra(start);

    cout << dist[end] << '\n';
    return 0;
}

피드백

다익스트라 알고리즘의 기본문제를 풀면서 알고리즘에 대해서 확실히 이해할 수 있었다.