[[problem:ROUTING]]

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

하지만, RTE가 발생하여 답답한 상황에 있습니다;;
(RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded))

제 생각에는, 메모리 제한이 65536KB 일때,
256KB*256KB = 65536KB 이므로 이론상 g[32768][32768] 배열을 만들수 있어 보입니다;
(근거.32768 * float(8byte) = 262144 byte = 256 KB)

즉, 생성한 배열 g[10000][10000] 은 float 를 8byte 로 했을때 충분해 보이는데, 왜 RTE 가 발생하는지 잘 모르겠습니다;;;

계산상 실수가 있는지.. 다른 원인이 있는지 고수님들의 조언을 부탁드립니다.

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

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

#define NUM 10000

int C;
int NN; // number of computers ; NN <= NUM
int edge; // 최대 20000 개
float g[NUM][NUM]; // 배열로 잡을 수 있는 크기는? 10억까지는 괜찮음..
float result;
float max;

float dijkstra(int src, int dest)
{
int N[NUM];
int Ni = 0;
float d[NUM];
int p[NUM];

float low = max;
int lowi = -1;

// init & set d[]
N[src] = 1;
Ni = 1;
for(int i=0;i<dest;i++) {
    d[i] = g[src][i];
    p[i] = -1;
}

while(Ni<NUM) { // dest ??
    /* 여기서 선언하면 NUM 이 큰 경우 죽는다..??? */
    //float low = max;
    //int lowi = -1;

    // find shortest path
    for(int i=0;i<dest;i++) {
        if(d[i] != -1 && d[i] != 0 && N[i] != 1 && low > d[i]) {
            low = d[i];
            lowi = i;
        }
    }
    N[lowi] = 1;
    Ni++;

    // update shortest path
    for(int i=0;i<dest;i++) {
        if(g[lowi][i] != -1 && g[lowi][i] != 0 && N[i] != 1) {
            if(d[i] == -1 || d[i] == 0 || d[i] > d[lowi] * g[lowi][i]) {
                d[i] = d[lowi] * g[lowi][i];
                p[i] = lowi;
            }
        }
    }
}

return d[dest-1];

}

int main(void)
{
//clock_t st = clock();

//freopen("input2.txt", "r", stdin);
//setbuf(stdout, NULL);

scanf("%d",&C);
for(int i=0;i<C;i++)
{
    scanf("%d %d", &NN, &edge);

    // init matrix
    for(int j=0;j<NUM;j++) {
        for(int k=0;k<NUM;k++) {
            g[j][k] = -1;
        }
        g[j][j] = 0;
    }

    max = 0;    // to find max edge

    // make matrix
    for(int j=0;j<edge;j++) {
        int x, y;
        float w;
        scanf("%d %d %f", &x, &y, &w);

        if(max < w)
            max = w;

        if(g[x][y] == -1 || (g[x][y] != -1 && g[x][y] > w))
            g[x][y] = g[y][x] = w;
    }

    max = max + 1;

    if(NN == 0 || NN == 1)
        result = 0;
    else
        result = dijkstra(0, NN);

    printf("%.10f\n", result);
}   

//printf("time : %d\n",clock()-st);

return 0;

}
~~~