글 읽기 - 시간초과 질문..

qkdtmdeh 6년 전 0

메모리 때문에 제 나름대로 인접리스트로 구현하였고, 시간 초과 해결을 위해 우선순위 큐를 이용하였는데도 시간초과가 납니다.

아무래도 이미 간선이 존재하는 상태에서 다시한 번 간선이 들어올수 있기에 즉 두 정점사이에 여러 간선 중 최소비용을 사용하는 간선만 사용하여야 시간초과를 피할 수 있을 것 같은데 어떻게 구현해야할지를 잘 모르겠습니다.

#include<stdio.h>
int a[20001];
int b[20001];
int c[20001];
int cnt[20001];
int chk[20001];
int cos[20001];
int qx[300001];
int qt[300001];
int st;
void quick(int left, int right)
{
    int s,t;
    int i,j;
    if(left<right)
    {
        s=a[(left+right)/2];
        i=left-1; j=right+1;
        while(1)
        {
            while(a[++i]<s);
            while(a[--j]>s);
            if(i>=j) break;
            t=a[i]; a[i]=a[j]; a[j]=t;
            t=b[i]; b[i]=b[j]; b[j]=t;
            t=c[i]; c[i]=c[j]; c[j]=t;
        }
        quick(left, i-1);
        quick(j+1, right);
    }
}//퀵소트

void up(int j)  
{   
    int t=0; 
    if(j>1)  
        if(qt[j]<qt[j/2])   
        {  
            t=qt[j]; 
            qt[j]=qt[j/2]; 
            qt[j/2]=t; 
    
            t=qx[j]; 
            qx[j]=qx[j/2]; 
            qx[j/2]=t; 
            
            up(j/2);  
        }  
} //upheap 함수
void down(int j)  
{  
    int smallest = j;  
    int l = j*2, r = j*2+1, t;    
    if (l<=st)  
        if (qt[l]<qt[smallest]) 
            smallest = l;  
    if (r<=st)  
        if (qt[r]<qt[smallest])  
            smallest = r;  
    if (smallest != j)  
    {  
        t=qt[j]; 
        qt[j]=qt[smallest]; 
        qt[smallest]=t; 
    
        t=qx[j]; 
        qx[j]=qx[smallest]; 
        qx[smallest]=t; 
        
        down(smallest);  
    }  
}  //downheap 함수
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
    int ss;
    scanf("%d", &ss);
    int i=0;
    for(i=1; i<=E; ++i)
    {
        scanf("%d %d %d", &a[i], &b[i], &c[i]);
        cnt[a[i]]++; //시작점으로써 들어온 각 개수를 세어준다.
    }
    for(i=1; i<=V; ++i)
    {
        cos[i]=1000000000;
        cnt[i]+=cnt[i-1]; //누적합으로해두고 밑에서 시작점을 기준으로 정렬하여 
						  //cnt[i-1]+1~cnt[i]가 i번 정점으로부터 나온 간선이되도록
    }
    quick(1, E);
    
    cos[ss]=0;
    qx[++st]=ss;
    qt[st]=0;
    while(1)
    {
        if(chk[qx[1]]==0) //이미 힙에서 빠져나온 정점은 이미 최소이고, 이전에 작업을 했기때문에 다시할 필요없음
        {
            chk[qx[1]]=1;
            cos[qx[1]]=qt[1];
            for(i=cnt[qx[1]-1]+1; i<=cnt[qx[1]]; ++i)
            {
                if(cos[b[i]]>qt[1]+c[i]&&c[i]!=1000000000)
                {
                    qx[++st]=b[i];
                    qt[st]=qt[1]+c[i];
                    cos[b[i]]=qt[1]+c[i];
                    up(st);
                }
            }
        }
        qx[1]=qx[st];
        qt[1]=qt[st];
        st--;
        if(st==0)
        {
            break;
        }
        down(1);
    }
    for(i=1; i<=V; ++i)
    {

        if(cos[i]==1000000000)
        {
            printf("INF\n");
        }
        else
        {
            printf("%d\n", cos[i]);
        }
    }
    
    
}

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

문제

문제

출처

ICPC

시간초과 질문..

qkdtmdeh 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말