[백준] 1915번 최소비용 구하기 C++ 풀이

문제

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

 

좀 까먹은 다익스트라를 다시해봤는데 헷갈리는 부분이 있어 정리한다. 

 

---

풀이

제목부터 다익스트라를 사용하는 문제.. 알고리즘을 모르면 풀 수 없으니 모르는 사람은 찾아보자.

정리해놓은걸 보면서 풀었는데, 질문게시판에도 나랑 비슷한 사람이 있고, 나도 헷갈리는 부분이 있어 정리해보았다. 

while(!pq.empty()){
    auto cur = pq.top();
    pq.pop();
    if(cur.X != board[cur.Y]) continue;
    for(auto nxt : edge[cur.Y]){
        if(nxt.X + board[cur.Y] >= board[nxt.Y]) continue;
        pq.push({nxt.X + board[cur.Y],nxt.Y});
        board[nxt.Y] = nxt.X + board[cur.Y];
    }
}

이 다익스타라 코드에서 처음에  if(cur.X != board[cur.Y]) continue;를 안넣었었다. 

이 코드가 없으면 시간초과가 나는데, 이 코드의 의미를 이해하지 못했었다.

pq를 이용한 다익스트라에서는 이미 노드까지의 최단거리가 확정되었더라도 다른경로로 방문할때 그 여부를 알 수 없다. 

for문 내부에서 확정시킨 최단거리와, pq에서 꺼낸 최단거리가 일치하지않는다면 그 경로는 최단경로가 아니므로 방문할 필요가 없다.

 

---

소스코드

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second

int N,M;
vector <pair<int,int>> edge[1001];
priority_queue <pair<int,int>,vector <pair<int,int>>,greater<pair<int,int>>> pq;
int board[1001];
const int INF = 100000000;
int main(){
    cin >> N >> M;
    int st, ds, cost;
    for (int i = 0; i < M; ++i) {
        cin >> st >> ds >> cost;
        edge[st].push_back({cost,ds});
    }
    int start, final;
    cin >> start >> final;
    for (int i = 1; i <= N; ++i) {
        board[i] = INF; //초기화
    }
    board[start] = 0;
    pq.push({0,start});
    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        if(cur.X != board[cur.Y]) continue;
        for(auto nxt : edge[cur.Y]){
            if(nxt.X + board[cur.Y] >= board[nxt.Y]) continue;
            pq.push({nxt.X + board[cur.Y],nxt.Y});
            board[nxt.Y] = nxt.X + board[cur.Y];
        }
    }
    cout << board[final];
}