글 읽기 - 런타임 에러 이유좀 알려주세요!

wistlin47 2년 전 0

out of bound 가 뜹니다 ㅠㅜㅜ 우선순위 큐를 한번 직접 구현해보았는데 어디서 넘어가는지 잘 모르겠습니다..

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define MMAX 20002
pair<int, int> Heap[MMAX];
int ans[MMAX];
int idx,V,E,Start;
vector<pair<int, int>>connect[MMAX];
void Push_Heap(int cost, int node){
    int i=++idx;
    while(i!=1 && cost<Heap[i/2].first){
        Heap[i]=Heap[i/2];
        i/=2;
    }
    Heap[i]={cost,node};
}
void Pop_Heap(){
    int parent=1;
    Heap[1]=Heap[idx--];
    while(1){
        int child=parent*2;
        if(child+1<=idx && Heap[child].first>Heap[child+1].first)
            child++;
        if(child>idx || Heap[child].first>Heap[parent].first) return;
        swap(Heap[child], Heap[parent]);
        parent=child;
    }
}
void Solve(){
    Push_Heap(ans[Start], Start);
    while(idx>0){
        int cost=Heap[1].first;
        int now=Heap[1].second;
        Pop_Heap();
        for(int i=0; i<connect[now].size(); i++){
            int ncost=connect[now][i].first;
            int next=connect[now][i].second;
            if(ans[next]>cost+ncost){
                ans[next]=cost+ncost;
                Push_Heap(ans[next], next);
            }
        }
    }
}
int main(){
    FAST;
    cin>>V>>E>>Start;
    fill(ans, ans+MMAX, INT_MAX);
    ans[Start]=0;
    
    int u,v,w;
    for(int i=0; i<E; i++){
        cin>>u>>v>>w;
        connect[u].push_back({w,v});
    }
    
    Solve();
    
    for(int i=1; i<=V; i++)
    {
        if(ans[i]==INT_MAX)
            cout<<"INF"<<'\n';
        else
            cout<<ans[i]<<'\n';
    }
}

euphoric_n 2년 전 0

정점의 갯수가 최대 20000개입니다.

out of bound 에러는 힙의 크기를 벗어나는 인덱스를 참조하고 있기 때문입니다.

트리의 높이는 (int)ceil(log2(20000)) = 15이고

힙의 크기는 2^15 = 32768 이상이어야 합니다.

wistlin47 2년 전 0

앗 감사합니다 이해했습니다

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

문제

문제

출처

ICPC

런타임 에러 이유좀 알려주세요!

wistlin47 2년 전 0

euphoric_n 2년 전 0

wistlin47 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말