글 읽기 - 다익스트라 코드인데 틀렸다고 떠요..

haya0206 6년 전 0

나무위키 문서보고 나름대로 구현한다음에 예제 넣어보니깐 잘되서 돌려봤는데..

그냥 틀렸다고 떠버리네요.

일단 check가 문제인가 싶어서

check 없애면 메모리 초과뜨고...

나무위키에서 설명한것과 같이 일단 처음값 = start면

dijk[start] = 0

이렇게 하고 처음값의 주변 노드를 우선순위 큐에 넣습니다..

넣으면서 if(dijk[a] + b.second < dijk[b.first]){ dijk[b.first] = dijk[a] + b.second; }

이런식으로 비교해서 dijk에 값을 넣는데요..틀렸을까요?

반례가 필요합니다..

#include <bits/stdc++.h>
using namespace std;
vector <pair<int,int> > vec[20001];
typedef pair<int, int> node;
vector <int> dijk(20001);
vector <int> check(20001);
struct cmp{
    bool operator()(node x,node y){
        return x.second > y.second;
    }
};
priority_queue<node, vector<node>, cmp> pq;
void dijkstra(int x){
    int a;
    pq.push(make_pair(x,0));
    while(!pq.empty()){
        a = pq.top().first;
        check[a] = 1;
        pq.pop();
        for(int i=0;i<vec[a].size();i++){
            node b = vec[a][i];
            if(check[b.first]==0){
                if(dijk[a] + b.second < dijk[b.first]){
                    dijk[b.first] = dijk[a] + b.second;
                }
                pq.push(b);
            }
        }
    }
}
int main(){
    int v,e,start,a,b,c;
    scanf("%d%d%d",&v,&e,&start);
    for(int i=0;i<e;i++){
        scanf("%d%d%d",&a,&b,&c);
        vec[a].push_back(make_pair(b,c));
    }
    for(int i=1;i<=v;i++){
        dijk[i] = 123456789;
    }
    dijk[start] = 0;
    dijkstra(start);
    for(int i=1;i<=v;i++){
        if(dijk[i]==123456789){
            printf("INK\n");
        }
        else
            printf("%d\n",dijk[i]);
    }
}

kimsy96 6년 전 3

INK -> INF

kimsy96 6년 전 0

음..나무위키에서 공부한다는 분은 처음보는거같아서 신기하네요

거기가 정확한지는 모르겠지만

차라리 책을 보시거나 아니면 백준 랭커님들 블로그 보는게 나을듯합니다

degurii 6년 전 0

INK 오타랑

26번줄에 pq에 push 해야할 건 b가 아니라 {b.first, dijk[b.first]}입니다

그렇게 고쳐도 시간초과가 뜨네요

degurii 6년 전 0

17줄 a가 이미 체크되어 있다면

해당 반복문을 실행하지 않고 넘겨야합니다ㅏ

16~19줄을

while(!pq.empty()){

a = pq.top().first;

pq.pop();

if(check[a]) continue;

check[a] = 1;

로 바꿔보세여

haya0206 6년 전 1

으아아악 오류가 넘처나는 코드였네요 모두감사합니다

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

문제

문제

출처

ICPC

다익스트라 코드인데 틀렸다고 떠요..

haya0206 6년 전 0

kimsy96 6년 전 3

kimsy96 6년 전 0

degurii 6년 전 0

degurii 6년 전 0

haya0206 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말