[[problem:PROMISES]]

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

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

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

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

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

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

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

~~~ c++
#include
//#include

#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;

}

</spoiler>