[백준 1753번] 최단경로 (C++)

아이디어

다익스트라 알고리즘을 사용하는데, Priority_queue를 이용해서 풀어야했다.

내가 자꾸 틀렸던건

            if(visited[nn] ==false && dist[nn] > dist[node]+nw)
            {
                dist[nn] = dist[node] +nw; //값을 갱신한다.
                pq.push({-(dist[node] +nw),nn}); // 이렇게 하면 맞습니다.
                //pq.push({-nw, nn});               //이렇게 하면 틀리고
            }

이부분인데 왜 누적합을 보내야하는지 의문이였다.

그런데, 찾고찾다가 아래와같은 반례를 볼 수 있었다.

(좌) : priority_queue에 간선 비용순으로 push했을 때

(우) : priority_queue에 간선 누적합 순으로 push했을 때 

 

C++ 풀이

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[20001];
priority_queue<pair<int,int>> pq;
bool visited[20001];
int dist[20001];
int V, E,K;
int INF = INT_MAX;

void dijk(int start)
{
    //스타트 지점은 0으로 시작.
    pq.push({0,start});
    dist[start] = 0;
    
    while(!pq.empty())
    {
        int weight=pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        //이미 방문했다면 최소일 것이므로 패스.
        if(visited[node] ==true) continue;
        
        //최소값으로 선택 됐을때 방문했다고 체크.
        visited[node] = true;

        for(int i = 0; i< v[node].size(); i++)
        {
            int nn = v[node][i].first; //next node의 노드 인덱스
            int nw = v[node][i].second; // next node의 weight정보(cost)

            //방문하지 않았던 노드이고, 새롭게 오는 거리정보가 기존 거리정보 보다 작으면 
            if(visited[nn] ==false && dist[nn] > dist[node]+nw)
            {
                dist[nn] = dist[node] +nw; //값을 갱신한다.
                pq.push({-(dist[node] +nw),nn}); // 이렇게 하면 맞습니다.
                //pq.push({-nw, nn});               //이렇게 하면 틀리고
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> V >> E >> K;
    //dist 높은값 설정.
    for(int i = 1; i<=V; i++)
    {
        dist[i] = INF;
    }
    
    //간선정보 입력
    for(int i = 0; i< E; i++)
    {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({e,w});
    }
    //다익스트라 실행
    dijk(K);
    
    //출력
    for(int i = 1; i<= V; i++)
    {
        if(dist[i] == INF) cout << "INF\n";
        else{
            cout << dist[i]<<'\n';
        }
    }
}