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

79愛的鼓勵 1訂閱站台

作法:最短路徑問題

想法:假設每一點是,做最短路徑,總和最小即是

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

#include<stdio.h>
#include<stdlib.h>
int map[30][30][2]={0};
int n,m,start,end,time=0;
main()
{
 while(scanf("%d %d",&n,&m)==2&&n!=0)
  {
   int a,b,c,x,y,data,maptop[1001]={0};
   char name[22][20]={0};
    for(a=1;a<=n;a++)
     scanf("%s",&name[a]);
    for(a=0;a<m;a++)
     {
      scanf("%d %d %d",&x,&y,&data);
      map[x][maptop[x]][0]=y;
      map[x][maptop[x]][1]=data;
      maptop[x]++;
      map[y][maptop[y]][0]=x;
      map[y][maptop[y]][1]=data;
      maptop[y]++;
     }
    int min=2147483647,ans;
    for(start=1;start<=n;start++)
    {
     int flag[1001]={0},way[1001]={0},find=0;
     flag[start]=1;
     for(a=1;a<=n;a++) way[a]=2147483647;
     way[start]=0;
     for(a=1;a<=n;a++)
      for(b=1;b<=n;b++)
        for(c=0;c<maptop[b];c++)
          if(flag[map[b][c][0]]==1)
            {
              int temp=(way[map[b][c][0]]+map[b][c][1]);
              way[b]=(temp<way[b])?temp:way[b];
              flag[b]=1;
            }   
       int sum=0;
       for(a=1;a<=n;a++) sum=sum+way[a];
       if(sum<min) {min=sum;ans=start;}
     }
     printf("Case #%d : %s\n",++time,name[ans]);
  }
 return 0;
}