글 읽기 - C++ 다익스트라 어느 부분이 잘못된건지 잘 모르겠습니다...

nmedt 1년 전 0

안티 라크소넨의 책에 나온 코드를 거의 그대로 썼습니다.

여러 케이스를 만들어 추적해보아도 어느 부분에서 틀린 것인지 도저히 모르겠습니다...

혹시 제가 다익스트라에 대해 잘못된 개념을 갖고 있거나 완전한 구현이 아닌걸까요...?

#include <bits/stdc++.h>
using namespace std;

#define INF 11

priority_queue<pair<int, int>> q;
vector<pair<int, int>> adj[20001];
int dist[20001];
int processed[20001];

void dijk(int S, int numV);

int main(void)
{
    int V, E, K;
    cin >> V >> E;
    cin >> K;

    for(int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    dijk(K, V);

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

    return 0;
}

void dijk(int S, int numV)
{
    for(int i = 1; i <= numV; i++) {
        dist[i] = INF;
    }

    dist[S] = 0; 
    q.push({0, S});
    while(!q.empty()) {
        int a = q.top().second; q.pop();
        if(processed[a]) {
            continue;
        }

        processed[a] = true;
        for(auto u : adj[a]) {
            int b = u.first, w = u.second;
            if(dist[a] + w < dist[b]) {
                dist[b] = dist[a] + w;
                q.push({-dist[b], b});
            }
        }
    }
}

bjh3502 1년 전 2

4 3

1 2 10

2 3 10

3 4 10

ans : 0 10 20 30

nmedt 1년 전 0

감사합니다 다시 짜보겠습니다!!

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

문제

문제

출처

ICPC

C++ 다익스트라 어느 부분이 잘못된건지 잘 모르겠습니다...

nmedt 1년 전 0

bjh3502 1년 전 2

nmedt 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말