글 읽기 - 혼자 힘으로 이해가 도저히 안되서 질문드립니다 !!

dudgh9661 3년 전 0

30~ 32 
47~49 라인을 지우면 정답으로 나오는데, 해당 라인들이 왜 있으면 안되는걸까요..???

30~32라인은 시작 노드와 연결된 노드의 값들을 미리 갱신해준것이고, 갱신된 노드들을 47~49라인을 통해서 미리 큐에 넣고 시작하려고 했는데..
46라인을 지우고 30~32라인, 47~49라인을 살려두면 52%에서 틀렸다고 나오네요 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000000

using namespace std;

int V, E, K;

vector< pair<int, int> > vec[20001];
int arr[20001] = { 0 };

void init() {
    cin >> V >> E;
    cin >> K;
    int start = K;
    int from, to, value;

    for(int i = 0; i <= V; i++) {
        arr[i] = INF;
    }

    for(int i = 0; i < E; i++) {
        cin >> from >> to >> value;
        vec[from].push_back({to, value});
    }

    arr[start] = 0;

    for(int i = 0; i < vec[start].size(); i++) {
        arr[vec[start][i].first] = vec[start][i].second;
    }



}

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if( a.second == b.second ) return a.first > b.first;
        return a.second > b.second;
    }
};
void dijkstra(int start) {
    priority_queue< pair<int, int> , vector< pair<int,int> >, cmp > pq;
    pq.push({start, 0});
    for(int i = 0; i < vec[start].size(); i++) {
        pq.push({vec[start][i].first, vec[start][i].second});
    }

    while ( !pq.empty() ) {
        int current = pq.top().first;
        int currentVal = pq.top().second;
        pq.pop();

        for(int i = 0; i < vec[current].size(); i++) {
            int next = vec[current][i].first;
            int nextVal = vec[current][i].second;

            if( arr[next] > currentVal + nextVal ) {
                arr[next] = currentVal + nextVal;
                pq.push({next, arr[next]});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
    dijkstra(K);

    for(int i = 1; i <= V; i++) {
        if( arr[i] == INF ) cout << "INF" << "\n";
        else cout << arr[i] << "\n";
    }

    return 0;
}

slah007 3년 전 2

시작점을 제외하고는 priority queue에 넣을 필요도, 답인 arr[]에 갱신해줄 필요도 없습니다.

시작점과 연결된 점들의 거리를 미리 갱신하면 후에 60번째 줄에서 갱신할 때 조건을 만족하지 못해 되어야 할 pq.push()가 생략될 수 있습니다.

dudgh9661 3년 전 0

해당 라인들이 존재해서 60번째 줄에서 조건을 만족하지 못해 pq.push가 안되는 경우는, 맨처음 시작점과 연결되어 있는 노드들을 que에 넣을 때 말고는 없지 않나요??

그래서 while문 돌리기 전에, 미리 47~59라인을 추가한것입니다.

물론, 해당 라인들을 없애면 더욱 깔끔한 코드가 되고 정상적으로 돌아가지만... 저 코드들이 존재했을때 틀리는 이유가 궁금합니다 ㅠ

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

문제

문제

출처

ICPC

혼자 힘으로 이해가 도저히 안되서 질문드립니다 !!

dudgh9661 3년 전 0

slah007 3년 전 2

dudgh9661 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말