글 읽기 - c 다익스트라 heap으로 구현했는데 시간초과가 뜹니다..

qefoi 1년 전 0

다익스트라 알고리즘을 우선순위큐를 이용하여 구현했는데 시간초과가 떠서 질문드립니다...

#include<stdio.h>
#include<stdlib.h>
#define INF 987654321
#define min(a,b) a<b?a:b

typedef struct node{
    struct node* next;
    int num;
    int w;
}NODE;

typedef struct{
    int num;
    int w;
}HEAP;

HEAP heap[200001];
int path[200001]; //계속 최소인 비용을 저장하는 배열
int check[200001];
NODE *arr[200001];

int cnt=1;

void heapfify(int idx){
    if(cnt-1>=idx*2+1){
        if(heap[idx*2].w>heap[idx*2+1].w){
            if(heap[idx*2+1].w<heap[idx].w){
                HEAP temp=heap[idx];
                heap[idx]=heap[idx*2+1];
                heap[idx*2+1]=temp;
                heapfify(idx*2+1);
            }
        }
        else{
            if(heap[idx*2].w<heap[idx].w){
                HEAP temp=heap[idx];
                heap[idx]=heap[idx*2];
                heap[idx*2]=temp;
                heapfify(idx*2);
            }
        }        
    }
    else if(cnt-1==idx*2){
        if(heap[idx].w>heap[idx*2].w){
            HEAP temp=heap[idx];
            heap[idx]=heap[idx*2];
            heap[idx*2]=temp;
            heapfify(idx*2);
        }
    }
    else ;
}

void insert(int idx){
    int temp=idx;
    while(temp/2>=1){
        if(heap[temp].w<heap[temp/2].w){
            HEAP x=heap[temp];
            heap[temp]=heap[temp/2];
            heap[temp/2]=x;
        }
        else break;
        temp/=2;
    }
    heapfify(temp);
}

int main()
{
    int v,e;
    scanf("%d %d",&v,&e);
    for(int i=1;i<=v;i++){
        arr[i]=(NODE*)malloc(sizeof(NODE));
        arr[i]->next=NULL;
        path[i]=INF;
    }
    
    int start;
    scanf("%d",&start);
    
    for(int i=0;i<e;i++){                   //인접 리스트 생성
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if(arr[a]->next==NULL){
            arr[a]->next=(NODE*)malloc(sizeof(NODE));
            arr[a]->next->num=b;
            arr[a]->next->w=c;
            arr[a]->next->next=NULL;
        }
        else{
            NODE* curr=arr[a];
            int flag=1;
            while(curr->next!=NULL){
                curr=curr->next;
                if(curr->num==b){
                    if(curr->w>c) curr->w=c;
                    flag=0;
                    break;
                }
            }
            if(flag){
                curr->next=(NODE*)malloc(sizeof(NODE));
                curr->next->num=b;
                curr->next->w=c;
                curr->next->next=NULL;
            }
        }
    }
    
    if(arr[start]->next!=NULL){        //start에서 바로 갈 수 있는 node들의 값을 path[]에 저장
        NODE* curr=arr[start]->next;
        check[start]=1;
        while(curr->next!=NULL){
            if(path[curr->num]>curr->w) {
                path[curr->num]=curr->w;
                heap[cnt].num=curr->num;
                heap[cnt].w=curr->w;
                insert(cnt);
                cnt++;
            }
            curr=curr->next;
        }
        if(path[curr->num]>curr->w) {
            path[curr->num]=curr->w;
            heap[cnt].num=curr->num;
            heap[cnt].w=curr->w;
            insert(cnt);
            cnt++;            
        }
    }
    
    while(1){                      //위와 비슷하게 다음 노드들을 계속 해서 진행
        int temp;
        int min=INF;
        if(cnt>1){
            temp=heap[1].num;
            min=heap[1].w;
            if(!check[temp]){
                HEAP x=heap[1];
                heap[1]=heap[cnt-1];
                heap[cnt-1]=x;
                cnt--;
                heapfify(1);
            }
            else {
                HEAP x=heap[1];
                heap[1]=heap[cnt-1];
                heap[cnt-1]=x;
                cnt--;
                heapfify(1);                
                continue;
            }
        }
        else break;            // heap에 아무것도 들어있지 않을때까지 반복문 돌림
        check[temp]=1;
        if(arr[temp]->next!=NULL){
            NODE* curr=arr[temp]->next;
            while(curr->next!=NULL){
                if(path[curr->num]>curr->w+min) {
                    path[curr->num]=curr->w+min;
                    heap[cnt].w=path[curr->num];
                    heap[cnt].num=curr->num;
                    insert(cnt);
                    cnt++;
                }
                curr=curr->next;
            }
            if(path[curr->num]>curr->w+min) {
                path[curr->num]=curr->w+min;
                heap[cnt].w=path[curr->num];
                heap[cnt].num=curr->num;
                insert(cnt);
                cnt++;                
            }
        }
    }
    for(int i=1;i<=v;i++) {
        if(i==start) printf("0\n");
        else if(path[i]==INF) printf("INF\n");
        else printf("%d\n",path[i]);
    }
    for(int i=1;i<=v;i++){
        NODE* curr=arr[i];
        while(curr->next!=NULL){
            NODE* temp=curr;
            curr=curr->next;
            free(temp);
        }
        free(curr);
    }
    return 0;
}

zjtlfk 1년 전 2

혹시, 입력을 받아 인접리스트에 추가하는 부분에서 매번 next가 null인 부분까지 가고있는지 확인해보세요

이러면 입력을 받을 때마다 리스트의 끝까지 찾아가느라 시간초과가 발생합니다

1달이 넘은 질문이라 보실지는 모르겠지만, 제가 오늘 겪었던 문제랑 비슷한 원인인것 같아 댓글 남겨봅니다..

qefoi 1년 전 1

와.. 덕분에 해결했습니다.. 감사합니다 ㅜㅠㅠ

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

문제

문제

출처

ICPC

c 다익스트라 heap으로 구현했는데 시간초과가 뜹니다..

qefoi 1년 전 0

zjtlfk 1년 전 2

qefoi 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말