최소비용 구하기 - 1916 백준

백준에서 가장 간단한 다익스트라 문제이다.

근데 겁나 헤맸다.

애초에 다른 로직은 맞는데 다익스트라의

이중 포문에서 내부 반복문이 없는 상태로

단 한 번만 갱신했더니 2%에서 계속 틀려서 멘탈이 나갔다.

다시 한 번 개념을 숙지해야겠다.

 

다익스트라라고 생각한 이유는,

음의 간선이 없고 정점(노드)의 개수가 크기 때문에 이를 선택했다.

 

 

난이도는 골드5

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

int INF = 210000000;
int n, m;
int price[1001][1001];
int dp[1001];
int x, y;
bool isVisited[1001] = { false };

void dijkstra(int start) {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 0; i < n; i++) {
            pq.push(make_pair(price[start][i], i));
            dp[i] = price[start][i];
        
    }

    for (int i = 0; i < n; i++) {
        int a = pq.top().second;
        pq.pop();
        if (isVisited[a] == true) continue;
        isVisited[a] = true;
        for (int j = 0; j < n; j++) {
            if (dp[j] > dp[a] + price[a][j]) {
                //x to y 의 길이가 x to a + a to y 까지의 길이보다 클 때..
                dp[j] = dp[a] + price[a][j];
                pq.push(make_pair(dp[j], j));
            }
        }

    }

}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                price[i][j] = 0;
            }
            else {
                price[i][j] = INF;
            }
            
        }
    }
    
    //M개의 BUS 출발점, 도착점, 가격
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (price[a - 1][b - 1] > c) {
            price[a - 1][b - 1] = c;
        }
        
    }
    cin >> x >> y;
    // INDEX
    x = x - 1;
    y = y - 1;
    //최단거리 찾기 => 음의 간선 없음, 점의 개수 많음, 다익스트라?
    dijkstra(x);
    cout << dp[y];
}