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

문제 및 풀이

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

다익스트라

시작 정점에서 도착 정점까지의 최소 비용을 구하는 문제. 다시말해 시작 정점부터 dfs로 탐색하며 특정 노드 i로 가는 최소값인 D[i]를 갱신한다.
현재 탐색하는 노드에 오기까지 필요한 비용을 기억해야 하기 때문에 큐에 입력할때 (cost : 현재까지의 이동 비용, next : 다음 탐색 노드) 를 넣어야 한다. 또한 방문 여부로 큐에 입력하는것이 아니라 값이 갱신되는 경우에 큐에 입력한다. 값이 갱신된 노드와 연결된 노드들만 값이 갱신될 수 있기 때문이다.

위상정렬 MST 다익스트라 풀때마다 헷갈려 죽겟다 ㅠㅠㅜ 풀때마다 기억 더듬으면서 푸니 시간 엄청 걸리는ㄷㅔ 노오력이 부족한것이겟지 .. 매일 조금씩 푸는걸 목표로 해야긋다
으으

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


const int INF = 987654321;

int N,M;
vector<pair<int, int>> v[1005];
int T[1005][1005];
int D[1005];
int a,b,c;
int start,dest;



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>N>>M;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(i!=j) T[i][j]=INF;

    for(int k=0; k<M; k++){
        cin>>a>>b>>c;
        //T[a][b]=min(T[a][b],c);
        v[a].emplace_back(c,b);
    }
    cin>>start>>dest;

    for(int i=1; i<=N; i++) D[i]=INF;

    priority_queue<pair<int, int>> pq;
    pq.push({0,start});

    while(!pq.empty()){

        int now = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();

        if(D[now]<cost) continue;

        for(int k=0; k<v[now].size(); k++){

            int next = v[now][k].second;
            int nextCost = cost + v[now][k].first;

            if(nextCost<D[next]){
                D[next] = nextCost;
                pq.push({(-1)*D[next],next});
            }

        }

    }


    cout<<D[dest];
}