作法:最大運輸量問題

利用相鄰矩陣加快

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

#include<stdio.h>
#include<stdlib.h>
int map[1001][200][2]={0};
int n,m,start,end;
main()
{
 while(scanf("%d %d",&n,&m)==2&&n!=0)
  {
   int a,b,c,x,y,data,maptop[1001]={0};
    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]++;
     }
    scanf("%d %d",&start,&end);
    int flag[1001]={0},way[1001]={0};
    flag[start]=1;way[start]=2147483647;
    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])?map[b][c][1]:way[map[b][c][0]];
             way[b]=(temp>way[b])?temp:way[b];
             flag[b]=1;
           }   
     printf("%d\n",way[end]);
  }
 return 0;
}