PROMISES 문제 알고리즘 문의 드립니다.

  • gloryof11
    gloryof11

    PROMISES

    안녕하세요 다익스트라 알고리즘을 공부하고 PROMISES 문제를 풀어 보았습니다.

    하지만, 시간 초과가 발생하여 답답한 상황에 있습니다;;

    주어진 도로로 최단 거리를 구해 놓고,

    이후 새로 추가되는 도로를 1개씩 추가하여 최단 거리가 변경되는지 체크하는게 제 알고리즘의 내용인데요..

    혹시 잘못된 알고리즘인지... 아니면 개선의 여지가 있는 알고리즘 인지..

    고수님들의 조언을 부탁드립니다.

    감사합니다. 좋은 하루 보내세요!

    #include <stdio.h>
    //#include <time.h>
    
    #define MAX_COST 100000
    #define NUM 200
    
    int TC;
    
    int V;  // 도시 수로 고정값 2~200
    int MM; // 현재 도로
    int NN; // 미래 도로 0<=M+N<=1000
    int g[NUM][NUM];
    int d[NUM][NUM];
    int p[NUM][NUM];
    
    // function 의 overflow 가 있는것 같은데,, 문제를 해결할줄 몰라서 전역변수로 선언...
    int ld[NUM][NUM];
    int lp[NUM][NUM];
    
    int N[NUM];
    int Ni = 0;
    int di[NUM];
    int pa[NUM];
    
    
    int dijkstra(void)
    {
        int enhanced = 0;
    
        // init
        for(int i=0;i<V;i++) {
            for(int j=0;j<V;j++) {
                ld[i][j] = 0;
                lp[i][j] = -1;
            }
        }
    
        // 기존 다익스트라를 for loop 으로 모든 src 에 대해 진행
        for(int i=0;i<V;i++) {
            // i 는 시작점
    
            // init
            for(int j=0;j<V;j++) {
                N[j] = 0;
                di[j] = g[i][j];
                pa[j] = -1;
            }
            N[i] = 1;
            Ni = 1;
    
            while(Ni<V) {
                int low = 999999;
                int lowi = -1;
    
                // find shortest path
                for(int j=0;j<V;j++) {
                    if(di[j] != -1 && di[j] != 0 && N[j] != 1 && low > di[j]) {
                        low = di[j];
                        lowi = j;
                    }
                }
                N[lowi] = 1;
                Ni++;
    
                // update shortest path
                for(int j=0;j<V;j++) {
                    if(g[lowi][j] != -1 && g[lowi][j] != 0 && N[j] != 1) {
                        if(di[j] == -1 || di[j] == 0 || di[j] > di[lowi] + g[lowi][j]) {
                            di[j] = di[lowi] + g[lowi][j];
                            pa[j] = lowi;
                        }
                    }
                }
            }
    
            // ld, lp 에 di, pa 를 입력
            for(int j=0;j<V;j++) {
                ld[i][j] = di[j];
                lp[i][j] = pa[j];
            }
        }
    
        // TODO ; return 1 if d[][] is updated, 0 if there is no update
        for(int i=0;i<V;i++) {
            for(int j=0;j<V;j++) {
                if(d[i][j] > ld[i][j] || (d[i][j] == -1 && ld[i][j] != -1))
                    enhanced = 1;
                d[i][j] = ld[i][j];
            }
        }
    
        if(enhanced > 0)
            return 1;
        else
            return 0;
    }
    
    int main(void)
    {
        //clock_t st = clock();
    
        //freopen("input.txt", "r", stdin);
        //setbuf(stdout, NULL);
    
        scanf("%d",&TC);
        for(int i=0;i<TC;i++)
        {
            int result = 0;
    
            // init
            for(int j=0;j<NUM;j++) {
                for(int k=0;k<NUM;k++) {
                    g[j][k] = -1;
                }
                g[j][j] = 0;
    
                for(int k=0;k<NUM;k++) {
                    d[j][k] = -1;
                    p[j][k] = -1;
                }
            }
    
            // input
            scanf("%d %d %d", &V, &MM, &NN);
    
            for(int j=0;j<MM;j++) {
                int src, dest, cost;
                scanf("%d %d %d", &src, &dest, &cost);
                g[src][dest] = cost;
                g[dest][src] = cost;
            }
    
            // 현재 g 로 기준 d[] 만듦
            dijkstra();
    
            for(int j=1;j<=NN;j++) {
                int src, dest, cost;
                scanf("%d %d %d", &src, &dest, &cost);
                g[src][dest] = cost;
                g[dest][src] = cost;
    
                // dijkstra 로 d[]' 만듦
                result += dijkstra();
            }
    
            printf("%d\n", NN-result);
        }   
    
        //printf("time : %d\n",clock()-st);
    
        return 0;
    }
    


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    시간복잡도를 구하신 뒤 최대 N을 대입해 보시면 시간 내에 돌아갈 여지가 있는지 감이 오실 것 같습니다.


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.