알고리즘 문제 AVOID에서 내가 제출한 틀린 답

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define TRUE 1

#define FALSE 0

#define MAX_VERTICES 150

#define MAX_ELEMENT 105

#define MAX 1000

#define MAX_DEST 10000

#define MAX_WEIGHT 2000000

int spotAmount=0;

int wayAmount=0;

int destAmount=0;

int destPt[MAX_DEST]={};

int weight[MAX_VERTICES][MAX_VERTICES]={};

int distance[MAX_VERTICES];

int found[MAX_VERTICES];

int allWay[MAX]={1,};

int passPoint[MAX_VERTICES][MAX]={1,};

int t[MAX]={1,};

int r[MAX]={1,};

int y[MAX]={1,};

int z[MAX]={1,};

int zz[MAX]={1,};

int isUsedPoint[MAX_VERTICES];

int nearPoint[MAX_VERTICES][MAX_VERTICES];

int nearPtCount[MAX_VERTICES];

int visited[MAX_VERTICES];

int level[MAX_VERTICES][MAX]={1,};

int backReturn[MAX_VERTICES][MAX]={1,};

int giftAmount[MAX_VERTICES][MAX]={1,};

int allRepeat=0;

int spotAmountTest;

int wayAmountTest;

int destAmountTest;

int wayTestA[5000];

int wayTestB[5000];

int wayTestC[5000];

int destTest[150];

 

 

// 0번째 칸에는 자리수를 저장합니다.

// 1번째 칸에는 1의 자리, 2번째 칸에는 10의 자리, 3번째 칸에는 100의 자리

// ... 등을 저장합니다. 최대 999자리까지 출력이 가능합니다.

int getNumSize(int a[])

{

 return a[0];

}

void printResult(int result[]) {

    int i, x;

    x=result[0];

    for(i=0;i<x;i+=1) {

        printf("%d", result[x-i]);

    }

}

void copy(int a[], int b[]) {

    int i, n=a[0];

    for(i=0;i<MAX;i+=1) { b[i]=a[i]; }

}

void clear(int a[]) {

    int i;

    for(i=0;i<MAX;i+=1) { a[i]=0; }

    a[0]=1;

}

int compare(int a[], int b[]) {

    int i=a[0];

    if(a[0]<b[0]) { return -1; }

    if(a[0]>b[0]) { return 1; }

    while(i>0) {

        if(a[i]<b[i]) { return -1;  }

        if(a[i]>b[i]) { return 1; }

        i-=1;

    }

    return 0;

}

void add(int a[], int b[], int r[]) {

    int i, j, x=0;

    clear(r);

    r[0]=a[0];

    if(b[0]>r[0]) { r[0]=b[0]; }

    for(i=1;i<=r[0];i+=1) {    // 수의 각 자리와 밑에서 올라온 수를

        x=a[i]+b[i]+x;         //  더해줍니다.

        r[i]=x%10;             // 값이 9보다 크면 제자리의 수만 남고

        x=x/10;                // 윗자리로 올라갑니다.

    }

    if(x!=0) {

        r[0]+=1;

        r[r[0]]=x;

    }

}

void sub(int a[], int b[], int r[]) {

    int i, j, x=0;

 

    clear(r);

    r[0]=a[0];

    if(b[0]>r[0]) { r[0]=b[0]; }

 

    for(i=1;i<=r[0];i+=1) { // 수의 각 자리로

        x=a[i]-b[i]+x;      // 결과에 더해줍니다.

        if(x<0) {

            r[i]=x+10;

            x=-1;

        } else {

            r[i]=x;

            x=0;

        }

    }

 

    if(x!=0) {

        for(i=0;i<a[0]+1;i+=1) { printf("%d ", a[i]); } printf("\n");

        for(i=0;i<b[0]+1;i+=1) { printf("%d ", b[i]); } printf("\n");

 

        printf("*****************ERROR*************\n");

        getchar(); getchar();

    }

    i=r[0];

    while(r[i]==0) { i-=1; }

    if(i==0) { i=1; }

    r[0]=i;

    //for(i=0;i<10;i+=1) { printf("%d ", r[i]); } printf("\n");

}

void mul(int a[], int b[], int r[]) {

    int i, j, x;

    clear(r);

    for(i=1;i<=b[0];i+=1) {         // 승수의 각 자리로

        for(j=1;j<=a[0];j+=1) {     // 피승수의 각자리를 곱합니다.

            r[i+j-1]+=b[i]*a[j];    // 결과에 더해줍니다.

            x=r[i+j-1];             // 값이 9보다 크면 윗자리로 올라갑니다.

            r[i+j-1]=x%10;          // 제자리의 수만 남고

            r[i+j] +=x/10;          // 윗자리로 올라갑니다.

        }

    }

    r[0]=a[0]+b[0];   // 결과의 자리수를 구합니다.

    if(r[r[0]]==0) { r[0]-=1; }

}

void div(int a[], int b[], int q[], int r[]) {

    int v1[MAX]={1,};

    int v2[MAX]={1,};

    int one[MAX]={1,1,};

    int two[MAX]={1,};

    int i, j, x, e1, e2, ex;

    double d1, d2, dd;

 

    copy(a, r); // 피제수를 나머지에 복사한다.

                // 당분간 나머지가 임시로 남아있는 피제수 노릇을 한다.

 

    d2=0;       // 제수의 근사값을 d2와 e2로 나타낸다.

    i=b[0];

    j=0;

    while(i>0 && j<15) {

        d2=10*d2+b[i];

        i-=1;

        j+=1;

    }

    e2=i;

 

    // 남아있는 피제수가 제수보다 클 동안 계속한다.

    while(compare(r, b)>=0) {

        // 피제수의 근사값을 d1과 e1으로 나타낸다.

        d1=0;                

        i=r[0];

        j=0;

        while(i>0 && j<15) {

            d1=10*d1+r[i];

            i-=1;

            j+=1;

        }   

        e1=i;

 

        // 임시 몫의 근사값을 dd와 ex로 나타낸다

        dd=d1/d2;           

 

        while(dd>10) { dd/=10; e1+=1; }

 

        ex=e1-e2+1;

 

        clear(v1);

        // 임시 몫은 v1이다. dd와 ex로 부터 v1을 구한다.

        v1[0]=ex;           

        i=0;

        while(ex>0&&i<10) {

            x=dd; dd-=x; dd*=10; v1[ex]=x; ex-=1; i+=1;

        }

 

        // v1이 클 경우 빼주는 값을 one이라한다.

        clear(one);         

        one[ex+1]=1;

        one[0]=ex+1;

 

        // v1의 아래 자리는 모두 0으로 채운다.

        if(i==0) {          

            while(ex>0) {

                v1[ex]=0; ex-=1;

            }

        }

 

        // 임시몫 v1이 너무 크다면 줄여준다.

        while(1) {

            // 임시 몫 v1과 제수를 곱한 결과를 v2라 한다.

            mul(v1, b, v2);

            // 임시 피제수가 v2보다 크다면 정상적으로 진행한다.

            if(compare(r,v2)>=0) { break; }

            // 만약 임시 피제수보다 v2가 크다면 위에서 구한 임시 몫 v1이 과도하게 크다.

            // v1에서 one을 빼준다.

            sub(v1, one, two);

            copy(two, v1);

        }

        // 임시 피제수에서 v2를 뺀 결과를 임시 피제수로 한다.

        sub(r, v2, two);

        copy(two, r);

        // q에 v1을 더한 결과를 q로 한다.

        add(q, v1, two);

        copy(two, q);

    }  

    // r에는 나머지가 남아 있게 된다.

}

typedef struct

{

 bool orum;

 int heap[MAX_ELEMENT];

 int dist[MAX_ELEMENT];

 int heap_size;

}HeapType;

void init(HeapType* h)

{

 h->heap_size=0;

 h->orum=false;

}

void insert_max_heap(HeapType* h,int item,int dist)

{

 int i;

 i=++(h->heap_size);

 if(h->orum==true)

 {

  while((i!=1)&&(dist<h->dist[i/2]))

  {

   h->heap[i]=h->heap[i/2];

   h->dist[i]=h->dist[i/2];

   i/=2;

  }

 }

 else

 {

  while((i!=1)&&(dist>h->dist[i/2]))

  {

   h->heap[i]=h->heap[i/2];

   h->dist[i]=h->dist[i/2];

   i/=2;

  }

 }

 h->heap[i]=item;

 h->dist[i]=dist;

}

int delete_max_heap(HeapType* h)

{

 int parent,child;

 int item,temp,tempDist;

 

 item=h->heap[1];

 tempDist=h->dist[(h->heap_size)];

 temp=h->heap[(h->heap_size)--];

 parent=1;

 child=2;

 while(child<=h->heap_size)

 {

  if(h->orum==true)

  {

   if((child<h->heap_size)&&(h->dist[child])>h->dist[child+1])

    child++;

   if(tempDist<=h->dist[child])

    break;

  }

  else

  {

   if((child<h->heap_size)&&(h->dist[child])<h->dist[child+1])

    child++;

   if(tempDist>=h->dist[child])

    break;

  }

  h->heap[parent]=h->heap[child];

  h->dist[parent]=h->dist[child];

  parent=child;

  child*=2;

 }

 h->heap[parent]=temp;

 h->dist[parent]=tempDist;

 return item;

}

int choose(int distance[],int n,int found[])

{

 int i,min,minpos;

 min=MAX_WEIGHT+1;

 minpos=-1;

 for(int i=0;i<n;i++)

 {

  if(distance[i]<min&&!found[i])

  {

   min=distance[i];

   minpos=i;

  }

 }

 return minpos;

}

void shortest_path(int start,int n)

{

 int i,u,w;

 for(i=0;i<n;i++)

 {

  distance[i]=weight[spotAmount-1][i];

  found[i]=FALSE;

 }

 found[spotAmount-1]=TRUE;

 distance[spotAmount-1]=0;

 int num;

 for(i=0;i<n-1;i++)

 {

  u=choose(distance,n,found);

  if(u==-1)

   continue;

  found[u]=TRUE;

  for(w=0;w<nearPtCount[u];w++)

  {

   num=nearPoint[u][w]-1;

   if(!found[num])

    if(distance[u]+weight[u][num]<distance[num])

     distance[num]=distance[u]+weight[u][num];

  }

 }

}

void bfsSearch(int point)

{

 HeapType q;

 init(&q);

 q.orum=false;

 clear(level[point]);

 level[point][0]=1;

 level[point][1]=1;

 

 visited[point]=TRUE;

 insert_max_heap(&q,point,distance[point]);

 int num;

 while(q.heap_size!=0)

 {

  point=delete_max_heap(&q);

  if(point==spotAmount-1)

  {

   clear(allWay);

   clear(passPoint[point]);

   copy(level[point],allWay);

   copy(level[point],passPoint[point]);

   continue;

  }

  isUsedPoint[point]=1;

  for(int i=nearPtCount[point]-1;i>=0;i--)

  {

   num=nearPoint[point][i]-1;

   if(isUsedPoint[num]==1)

    continue;

   if(distance[point]==distance[num]+weight[point][num])

   {

    if(visited[num]!=1)

    {

     insert_max_heap(&q,num,distance[num]);

     visited[num]=1;

    }

    clear(r);

    clear(t);

    r[1]=1;

    add(giftAmount[point],r,t);

    clear(giftAmount[point]);

    copy(t,giftAmount[point]);

    clear(r);

    add(level[num],level[point],r);

    clear(level[num]);

    copy(r,level[num]);

   }

  }

  clear(r);

  r[1]=1;

  if(compare(giftAmount[point],r)==1&&point!=0)

  {

   int pt=point;

   clear(r);

   clear(backReturn[pt]);

   r[1]=1;

   sub(giftAmount[pt],r,backReturn[pt]);

   HeapType rq;

   init(&rq);

   rq.orum=true;

   int rVisited[MAX_VERTICES];

   for(int j=0;j<MAX_VERTICES;j++)

    rVisited[j]=0;

   rVisited[pt]=TRUE;

   insert_max_heap(&rq,pt,distance[pt]);

   int numm;

   while(rq.heap_size!=0)

   {

    pt=delete_max_heap(&rq);

 

    for(int i=nearPtCount[pt]-1;i>=0;i--)

    {

     numm=nearPoint[pt][i]-1;

     if(visited[numm]==0)

      continue;

     if(distance[pt]!=distance[numm]+weight[pt][numm])

     {

      if(rVisited[numm]!=1)

      {

       insert_max_heap(&rq,numm,distance[numm]);

       rVisited[numm]=1;

      }

     

      clear(r);

      add(backReturn[numm],backReturn[pt],r);

      clear(backReturn[numm]);

      copy(r,backReturn[numm]);

      clear(r);

      mul(backReturn[pt],level[numm],r);

      clear(t);

      add(passPoint[numm],r,t);

      clear(passPoint[numm]);

      copy(t,passPoint[numm]);

     }

    }

    clear(backReturn[pt]);

   }

  }

  clear(r);

  clear(t);

  mul(level[point],giftAmount[point],r);

  add(r,passPoint[point],t);

  clear(passPoint[point]);

  copy(t,passPoint[point]);

  clear(giftAmount[point]);

 }

}

 

int main()

{

 int repeat=0;

 int ptFrom,ptTo,weightNum;

 scanf("%d",&repeat);

 if(repeat>50||repeat<1)

 {

  exit(0);

 }

 for(int m=0;m<repeat;m++)

 {

  allRepeat=m;

  scanf("%d %d %d",&spotAmountTest,&wayAmountTest,&destAmountTest);

  if(spotAmountTest>100||spotAmountTest<2||wayAmountTest>spotAmountTest*(spotAmountTest-1)/2||wayAmountTest<0||destAmountTest>spotAmountTest||destAmountTest<1)

   exit(0);

  for(int j=0;j<wayAmountTest;j++)

  {

   scanf("%d %d %d",&wayTestA[j],&wayTestB[j],&wayTestC[j]);

   if(wayTestA[j]>spotAmountTest||wayTestA[j]<1||wayTestB[j]>spotAmountTest||wayTestB[j]<1||wayTestC[j]>10000||wayTestC[j]<1)

    exit(0);

  }

  for(int j=0;j<destAmountTest;j++)

  {

   scanf("%d",&destTest[j]);

   if(destTest[j]<1||destTest[j]>spotAmountTest)

    exit(0);

  }

 

  for(int i=0;i<MAX_DEST;i++)

  {

   destPt[i]=0;

  }

  spotAmount=spotAmountTest;

  wayAmount=wayAmountTest;

  destAmount=destAmountTest;

 

  clear(allWay);

  for(int i=0;i<MAX_VERTICES;i++)

  {

   for(int j=0;j<MAX_VERTICES;j++)

   {

    weight[i][j]=0;

    nearPoint[i][j]=0;

   }

   clear(level[i]);

   clear(giftAmount[i]);

   clear(passPoint[i]);

   clear(backReturn[i]);

  }

  for(int i=0;i<MAX_VERTICES;i++)

  {

   visited[i]=0;

   nearPtCount[i]=0;

   isUsedPoint[i]=0;

   distance[i]=0;

   found[i]=0;

   for(int j=i+1;j<spotAmount;j++)

   {

    weight[i][j]=MAX_WEIGHT;

    weight[j][i]=MAX_WEIGHT;

   }

   weight[i][i]=0;

  }

 

  for(int i=0;i<wayAmount;i++)

  {

   ptFrom=wayTestA[i];

   ptTo=wayTestB[i];

   weightNum=wayTestC[i];

   if(ptFrom<1)

    ptFrom=1;

   else if(ptFrom>spotAmount)

    ptFrom=spotAmount;

   if(ptTo<1)

    ptTo=1;

   else if(ptTo>spotAmount)

    ptTo=spotAmount;

   if(weightNum<1)

    weightNum=1;

   else if(weightNum>10000)

    weightNum=10000;

   if(ptFrom==ptTo)

    continue;

   if(weight[ptFrom-1][ptTo-1]!=MAX_WEIGHT)

   {

    if(weight[ptFrom-1][ptTo-1]>weightNum)

    {

     weight[ptFrom-1][ptTo-1]=weightNum;

     weight[ptTo-1][ptFrom-1]=weightNum;

    }

   }

   else

   {

    nearPoint[ptFrom-1][nearPtCount[ptFrom-1]]=ptTo;

    nearPtCount[ptFrom-1]++;

    nearPoint[ptTo-1][nearPtCount[ptTo-1]]=ptFrom;

    nearPtCount[ptTo-1]++;

    weight[ptFrom-1][ptTo-1]=weightNum;

    weight[ptTo-1][ptFrom-1]=weightNum;

   }

  }

 

  for(int i=0;i<destAmount;i++)

  {

   destPt[i]=destTest[i];

  }

 

 

  shortest_path(0,spotAmount);

 

  isUsedPoint[0]=1;

  bfsSearch(0);

 

  clear(z);

  if(compare(z,allWay)==0)

  {

   for(int i=0;i<destAmount;i++)

   {

    printf("0/1\n");

   }

   continue;

  }

 

  int index;

  for(int i=0;i<destAmount;i++)

  {

  

   index=destPt[i]-1;

   clear(r);

   clear(t);

   clear(y);

   copy(passPoint[index],t);

   copy(allWay,r);

   if(t[0]==1&&t[1]==0)

   {

    printf("0/1\n");

    continue;

   }

   else if(compare(r,t)==0)

   {

    printf("1/1\n");

    continue;

   }

   else if(compare(t,r)==1)

   {

    while(1) long long* mk=(long long*)malloc(sizeof(long long));

   }

  

   clear(zz);

   clear(z);

   zz[1]=1;

   while(!(compare(t,zz)==0||compare(t,z)==0))

   {

    sub(r,t,y);

    copy(y,r);

    if(compare(r,t)==-1)

    {

     copy(r,y);

     copy(t,r);

     copy(y,t);

    }

   }

  

   if(t[0]==1&&t[1]==1)

   {

    printResult(passPoint[index]);

    printf("/");

    printResult(allWay);

    printf("\n");

   }

   else

   {

    clear(y);

    clear(t);

    div(passPoint[index],r,y,t);

    printResult(y);

    printf("/");

    clear(y);

    clear(t);

    div(allWay,r,y,t);

    printResult(y);

    printf("\n");

   }

  }

 }

 return 0;

}