摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:Floyd-Warshall 演算法

/**************************************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n;
 while(scanf("%d",&n)==1&&n!=0)
   {
     int map[100][100]={0};
     int a,b,c;
     for(a=0;a<n;a++)
      for(b=0;b<n;b++)
       {
         scanf("%d",&map[a][b]);
         if(map[a][b]==0) map[a][b]=1000000;
       }
      for(a=0;a<n;a++)
       for(b=0;b<n;b++)
        for(c=0;c<n;c++)
         if(map[b][a]+map[a][c]<map[b][c])
          map[b][c]=map[b][a]+map[a][c];
       int min=1000000;
       for(a=0;a<n;a++)
        if(min>map[a][a]) min=map[a][a];
      if(min!=1000000) printf("%d\n",min);
      else printf("-1\n");
   }
 return 0;
}

/*****************************************************/

優化輸入

#include<stdio.h>
#include<stdlib.h>
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
 int n;
 while(scanf("%d",&n)==1&&n!=0)
   {
     int map[100][100]={0};
     int a,b,c;
     for(a=0;a<n;a++)
      for(b=0;b<n;b++)
       {
         map[a][b]=input();
         if(map[a][b]==0) map[a][b]=1000000;
       }
      for(a=0;a<n;a++)
       for(b=0;b<n;b++)
        for(c=0;c<n;c++)
         if(map[b][a]+map[a][c]<map[b][c])
          map[b][c]=map[b][a]+map[a][c];
       int min=1000000;
       for(a=0;a<n;a++)
        if(min>map[a][a]) min=map[a][a];
      if(min!=1000000) printf("%d\n",min);
      else printf("-1\n");
   }
 return 0;
}