(C++) - 백준(BOJ) 1916번 : 최소비용 구하기

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

다익스트라 문제였습니다.

 

풀이방법

 1. 도시 사이에 연결된 간선과 가중치를 vector<pait<int,int>> 자료구조 graph변수에 저장합니다.

 2. 출발도시부터 i도시까지의 최소비용을 저장할 변수 dist배열 선언 후 모든 값을 큰수 INF로 초기화 합니다.

 3. dijsktra 함수를 실행합니다.

    3-1. dist[startCity] = 0 입니다. 출발도시의 최소비용은 0이기 때문입니다.

    3-2. minHeap인 priority queue pq변수를 선언합니다. first는 해당 도시까지의 비용, 도시 번호가 주어집니다.

    3-3. 도시 cur로 가는데 드는 비용은 curCost입니다. cur과 연결된 다른 도시들을 모두 확인합니다. 도시 next로 가는데 드는 비용은 nextCost입니다. dist[next] 보다 현재도시를 거쳐 next로 가는 비용이 더 작다면 dist[next]를 갱긴해줍니다. 그 후 해당 도시를 거쳐갔으므로 dist[next],next를 push해줍니다.

   

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using vii = vector<pair<int,int>>;
using pii = pair<int,int>;
int n,m, startCity, endCity, dist[1001];
vii graph[1001];

int dijsktra(){
    dist[startCity] = 0;
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push({0,startCity});
    while(!pq.empty()){
        int curCost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(curCost > dist[cur])continue;
        for(int i = 0; i < graph[cur].size(); i++){
            int nextCost = graph[cur][i].second;
            int next = graph[cur][i].first;
            if(dist[next] <= curCost + nextCost) continue;
            dist[next] = curCost + nextCost;
            pq.push({dist[next],next});
        }
    }
    return dist[endCity];
}
int main(){
    cin >> n >> m;
    for(int i = 0; i <= n; i++) dist[i] = INF;

    while(m--){
        int u,v,w;
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
        
    }

    cin >> startCity >> endCity;
    cout << dijsktra() <<'\n';

}