백준, BOJ, 1916번, 최소비용 : C++ [CPP] ★★★

다익스트라 알고리즘 또 까먹었다.

오늘은 3문제 정도 풀어봐야겠다.

 

 

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

 

 

---

 

 

#맞는 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

#define MAX 1001  // 1000개 정도면 인접행렬 만들만하다.
#define INF 987654321 //적당히 큰 숫자여야한다.

using namespace std;

int N; //도시 수
int M; //버스 수

int st, ed; //시작노드, 목표노드

vector<pair<int,int>> adj[MAX]; //벡터를 넣는 배열 {거리, 노드}
int dist[MAX]; //최소거리 테이블

void dijkstra(){
    dist[st] = 0; //전역으로 시작노드를 받음.
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
    heap.push({dist[st], st});
    
    while(!heap.empty()){
        auto cur = heap.top();
        heap.pop();
        int distance = cur.first;
        int idx = cur.second;
        
        if(dist[idx] < distance)continue; //이미 처리했던 노드(최소비용이 확정된 노드라면)지나감
        
        for(auto next : adj[idx]){
            int nextD = next.first;
            int nidx = next.second;
            //이렇게 지나가는 것이 더 작다면
            if(dist[nidx] > dist[idx] + nextD){
                dist[nidx] = dist[idx] + nextD;
                heap.push({dist[nidx], nidx});
            }
        }
    }
}

int main(){
    cin >> N >> M;
    for(int i = 0; i<=N; i++){
        dist[i] = INF;
    }
    
    for(int i = 0; i<M; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back({cost,to}); //거리, 노드
    }
    //시작노드 목표노드
    cin >> st >> ed;
    
    dijkstra();
    
    cout << dist[ed];
    
    
    return 0;
}

 

다익스트라는 익히려면 많이 풀어봐야겠다.