[백준/C++] 1916번 : 최소비용 구하기

 

 

풀이

• A -> B로 가는데 드는 최소비용을 구하는 문제이다
• 각 버스의 출발 도시와 도착 도시, 버스 비용을 그래프에 추가한다.
• 같은 출발 도시에서 여러 개의 버스가 있을 수 있으므로, 출발 도시를 인덱스로 하는 벡터에 도착 도시와 비용을 추가한다.
• 우선순위 큐를 사용하여 탐색할 도시와 그 도시까지의 비용을 저장하고, 시작 도시의 거리는 0으로 설정하고 큐에 추가한다.
• 큐에서 도시를 하나씩 꺼내면서 인접한 도시들을 탐색한다.
• 구간 출발점에서 도착점까지의 최소 비용인 distance[B]를 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

struct Edge {
    int destination;
    int cost;
};

vector<vector<Edge>> graph;

vector<int> Dijkstra(int start, int N) {
    vector<int> distance(N + 1, INF);
    priority_queue<pair<int, int>> pq;
    distance[start] = 0;
    pq.push(make_pair(0, start));

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

        if (currCost > distance[curr])
            continue;

        for (const auto& edge : graph[curr]) {
            int next = edge.destination;
            int nextCost = currCost + edge.cost;

            if (nextCost < distance[next]) {
                distance[next] = nextCost;
                pq.push(make_pair(-nextCost, next));
            }
        }
    }

    return distance;
}

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

    graph.resize(N + 1);

    for (int i = 0; i < M; i++) {
        int start, destination, cost;
        cin >> start >> destination >> cost;
        graph[start].push_back({ destination, cost });
    }

    int A, B;
    cin >> A >> B;

    vector<int> distance = Dijkstra(A, N);

    cout << distance[B] << endl;

    return 0;
}

 

 

 

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

1916번: 최소비용 구하기