[情報] 資料結構作業-趴萬

[gink11400 (湯圓)]

#include<stdio.h>
#include<stdlib.h>
int N,E;
int found[50];
long int A[50][50];
int part1[50],part2[50][50];
void shortestpath();
void allcosts();

void main()
{
        FILE *fptr;
        int i,j;
    long int weight;

        fptr = fopen("1111.txt","r");
    if (fptr == NULL)
                exit(1);
    fscanf(fptr, "%d" , &N);
        fscanf(fptr, "%d" , &E);
        for (i=0;i<N;i++)
        {
                for (j=0;j<N;j++)
                {
                        if (i==j) {A[i][j]=0;}
                        else {A[i][j]=1000;}
                }
        }

while (fscanf(fptr,"%d %d %ld",&i,&j,&weight) != EOF)
                A[i][j] = weight;
        fclose(fptr);

        printf("part1:");
    shortestpath();
        printf("\npart2: \n");
        allcosts();
}
void shortestpath()
{
        int found[100];
    int i,j,small,u;

        for(i=0;i<N;i++)
        {
                found[i] = 0;
                part1[i] = A[0][i];
        }
        found[0] = 1;

        for (i=0;i<N-2;i++)
    {
                u=1000;
                for (j=0 ; j<N ; j++)
                {
             if (found[j] == 0)
                         {
                                if (u > part1[j])
                                {
                                        small = j;
                                    u = part1[j];
                                }
                         }
                }
                found[small] = 1;
                for (j=0;j<N;j++)
            if (found[j] == 0)
                          if (part1[small] + A[small][j] < part1[j])
                                        part1[j] = part1[small] + A[small][j];
        }
        for (i=0;i<N;i++)
        {
                if (i<N-1)  {printf("%2d,",part1[i]);}
                else {printf("%2d",part1[i]);}
        }
}
void allcosts()
{
    int i,j,k;
        for (i=0;i<N;i++)
                for (j=0;j<N;j++)
                        part2[i][j] = A[i][j];
        for (k=0;k<N;k++)
        for (i=0;i<N;i++)
                    for (j=0;j<N;j++)
                                if (part2[i][k] + part2[k][j] < part2[i][j])
                                        part2[i][j] = part2[i][k] + part2[k][j];

        for (i=0;i<N;i++)
        {
                for (j=0;j<N;j++)
                {
                        if (part2[i][j]>=1000) {printf("   -");}
                        else {printf("%4d",part2[i][j]);}
                }
                printf("\n");
        }
}
}

=======================================================================

還沒去驗的人快去唷~~~
我也不知道還能不能驗
反正第二次作業也要驗了
第一次沒驗的就一起去驗八
有驗總比沒驗好!!

--
 『Together』就是  To + get + her  由此可知當初造字的人
  是在告訴我們-----
  想在『一起』就要
                                   ㄧ○︿   去  把  她
                                      \
                                    √ ﹀...

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.131.89.114