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

79愛的鼓勵 1訂閱站台

在此先說,不一定正確!

輸入說明:

第一行會有兩個數字 n m ,n代表圖形上會有1~n個點,m代表接下來會有m筆關係

接下來的m行,每行的前兩個數字為此兩點有連結(雙向),第三個數字代表之間的最大運輸量

範例輸入:

7 10
1 2 32
1 6 3
2 6 7
2 3 21
2 5 12
3 5 6
3 7 11
5 4 13
4 7 9
3 6 2

範例輸出:

1 -> 1 MAX : ∞
1 -> 2 MAX : 32
1 -> 3 MAX : 21
1 -> 4 MAX : 12
1 -> 5 MAX : 12
1 -> 6 MAX : 7
1 -> 7 MAX : 11
2 -> 1 MAX : 32
2 -> 2 MAX : ∞
2 -> 3 MAX : 21
2 -> 4 MAX : 12
2 -> 5 MAX : 12
2 -> 6 MAX : 7
2 -> 7 MAX : 11
3 -> 1 MAX : 21
3 -> 2 MAX : 21
3 -> 3 MAX : ∞
3 -> 4 MAX : 12
3 -> 5 MAX : 12
3 -> 6 MAX : 7
3 -> 7 MAX : 11
4 -> 1 MAX : 12
4 -> 2 MAX : 12
4 -> 3 MAX : 12
4 -> 4 MAX : ∞
4 -> 5 MAX : 13
4 -> 6 MAX : 7
4 -> 7 MAX : 11
5 -> 1 MAX : 12
5 -> 2 MAX : 12
5 -> 3 MAX : 12
5 -> 4 MAX : 13
5 -> 5 MAX : ∞
5 -> 6 MAX : 7
5 -> 7 MAX : 11
6 -> 1 MAX : 7
6 -> 2 MAX : 7
6 -> 3 MAX : 7
6 -> 4 MAX : 7
6 -> 5 MAX : 7
6 -> 6 MAX : ∞
6 -> 7 MAX : 7
7 -> 1 MAX : 11
7 -> 2 MAX : 11
7 -> 3 MAX : 11
7 -> 4 MAX : 11
7 -> 5 MAX : 11
7 -> 6 MAX : 7
7 -> 7 MAX : ∞

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

#include<stdio.h>
#include<stdlib.h>
int map[201][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]++;
     }
    for(start=1;start<=n;start++)
    {
    int flag[1001]={0},way[1001]={0},find=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;
           }   
     for(a=1;a<=n;a++)
       if(a!=start)
       printf("%d -> %d MAX : %d\n",start,a,way[a]);
       else
       printf("%d -> %d MAX : ∞\n",start,a);
    }
  }
 return 0;
}