백준 1916번, 최소비용 구하기(C, C++)

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

#define INF 100000000;

using namespace std;

vector<pair<int, int>> a[1001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>>pq;
int d[1001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    int M;
    int start;
    int end;
    cin>>N>>M;
    for(int i = 1; i <= N; i++){
        d[i] = INF;
    }
    for(int i = 1; i <= M; i++){
        int x, y, z;
        cin>>x>>y>>z;
        a[x].push_back({y, z});
    }
    cin>>start>>end;
   
    pq.push(make_pair(0, start));
    d[start] = 0;
    while(!pq.empty()){
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(d[cur] < cost){
            continue;
        }
        for(int i = 0; i < a[cur].size(); i++){
            int Next = a[cur][i].first;
            int ncost = a[cur][i].second;
            if(d[Next] > cost + ncost){
                d[Next] = cost + ncost; //  
                pq.push(make_pair(d[Next], Next));
            }
        }
    }
    cout<<d[end]<<endl;
    return 0;
}

 

 

 

문제에 나와 있는 예제를 이용해 그림을 그렸습니다.

동그라미를 마을이라고 생각하고 간선을 버스라고 생각하였습니다.

 

최소비용을 구해야하므로

다익스트라 알고리즘을 이용해 풀기로 했습니다.

​

​

간선에 저장할 정보는 시작위치와 끝나는 위치, 그리고 비용이 얼마나 드는지를 저장하기위해

vector<pair<int, int>> a[1001]을 선언하여 세가지의 정보를 저장을 합니다.

for문을 이용한 Dist의 약자인 d배열을 INF로 설정합니다.

​

그리고

우선순위 큐를 이용하도록 합니다.

힙의 구조를 갖고 있고 기본적으로 우선순위 큐의 우선순위는 값이 높은 순으로 배치되어있으므로

값이 낮은 순으로 우선순위가 배치되도록 합니다.

 

코드 안에 if(d[cur] < cost)는

(d는 dist의 약자)

 

1과 연결된 2번 정점의 dist[2]값과 위치가 큐에 들어가고 그 다음 1번 정점과 3번 정점이 연결된 dist[3]값과 위치가 들어갑니다.

 

2번정점은 3번 정점과 연결되어 있어 dist[3]을 새롭게 갱신할 수 있습니다.

2번 정점이 3번 정점과 4번 정점을 큐에 넣는 과정을 거치고나면

dist[3] = 2 + 4 = 6이 되어있을 것이며,

3번 정점은 앞서 1번 정점과 3번 정점이 연결되어서 생긴 cost 값이 3입니다.

if(dist[cur] < cost){

continue;}

위의 경우는 해당 조건에 부합하지 않아 continue문을 실행하지 않습니다.

만약 cost가 dist[cur]가 더 크다면 저희가 구하고자하는 것은 최소비용이므로 

해당 방향으로 진행한다면 최소비용을 구할 수 없기 때문에 continue문을 쓰는 것이 맞습니다.