글 읽기 - 왜 우선순위큐에 누적합 정보를 넣어줘야하나요 ?

hyeon0528 3년 전 0

문제가 되는 라인은 38, 39번 라인입니다.

39번 라인으로하면 계속 최소비용을 가지는 간선을 우선적으로 방문할 것이라 생각해서 저렇게 짰었는데

계속 틀리더군요,

38번 라인처럼 누적합으로하니 맞다고 하는데,

둘다 주어진 테스트 케이스는 잘 통과합니다.

왜 간선정보만으로 선택하면 안되는것인가요 ?

혼자서 테스트케이스 바꿔가면서 하는데 도통 찾을수가 없네요 ㅠㅠ

고수님들의 고견 기다리겠습니다.

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[20001];
priority_queue<pair<int,int>> pq;
queue<int> q;
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';
        }
    }
}

hyeon0528 3년 전 1

https://www.acmicpc.net/board/...

저와 같은 고민이신분은 여기를...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 우선순위큐에 누적합 정보를 넣어줘야하나요 ?

hyeon0528 3년 전 0

hyeon0528 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말