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

[문제]

1916번: 최소비용 구하기 (acmicpc.net)

1916번: 최소비용 구하기

[문제 풀이]

다익스트라를 이용한 기초적인 문제이다.

pair<int, int>를 사용해서 graph[현재위치].first 는 목표지점, graph[현재위치].second 는 거리로 입력을 받고 풀었다.

다익스트라 알고리즘을 만들때는 우선순위 큐를 이용해서 오름차순으로 (거리,목표지점)을 만들었고 우선순위 큐의 크기가 0 이상일때는 계속해서 실행이 되며 distance 벡터를 고치도록 만들었다.

나의 경우는 다익스트라 알고리즘을 글로 봐서는 이해가 잘 안되었기에 유튜브(바킹덕님 강의) 를 참고해서 공부를 하였다.

플로이드-워셜처럼 알고리즘을 제대로 외우면 생각보다 잘 외워지는 알고리즘이니 꼭 강의등을 참고해서 이해를 제대로 하고 넘어가도록 하자.

[어려웠던 점]

정점(도시의 개수)는 최대 1,000개이고 간선의 비용(버스 비용)은 최대 100,000이니 나올 수 있는 최대거리값이 1,000,000,000이 최대였다.

그렇기에 distance 벡터를 만들때 초기화 값을 10억 이상으로 둬야 문제가 발생하지 않는데 해당 부분을 100만으로 두었다가 4번이상 틀리면서 헤매었다.(44%에서 오류 발생)

*다익스트라를 만들 때 최대값에 주의하도록 하자.

[코드]

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

using namespace std;

vector<pair<int, int> > graph[1001];

vector<int> dijkstra(int start,int vertex){
    vector<int> distance(vertex,1000000000);
    distance[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int> > ,greater<pair<int, int> > > pq;
    pq.push(make_pair(0,start));

    while(pq.size() > 0){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if(distance[cur] != cost){
            continue;
        }

        for(int i = 0;i<graph[cur].size();i++){
            int next = graph[cur][i].first;
            int nCost = graph[cur][i].second;

            if(distance[next] <= nCost + cost){
                continue;
            }
            distance[next] = nCost + cost;
            pq.push(make_pair(nCost + cost, next));
        }
    }

    return distance;
}


int main(){
    int n,m;
    cin>>n>>m;
    n++;
    for(int i = 0;i<m;i++){
        int source,destination,cost;
        cin>>source>>destination>>cost;
        graph[source].push_back(make_pair(destination,cost));
    }
    int start,end;
    cin>>start>>end;

    vector<int> answer = dijkstra(start,n);

    cout<<answer[end]<<endl;

    return 0;
}