摸索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 MIN : 0
1 -> 2 MIN : 10
1 -> 3 MIN : 5
1 -> 4 MIN : 24
1 -> 5 MIN : 11
1 -> 6 MIN : 3
1 -> 7 MIN : 16
2 -> 1 MIN : 10
2 -> 2 MIN : 0
2 -> 3 MIN : 9
2 -> 4 MIN : 25
2 -> 5 MIN : 12
2 -> 6 MIN : 7
2 -> 7 MIN : 20
3 -> 1 MIN : 5
3 -> 2 MIN : 9
3 -> 3 MIN : 0
3 -> 4 MIN : 19
3 -> 5 MIN : 6
3 -> 6 MIN : 2
3 -> 7 MIN : 11
4 -> 1 MIN : 24
4 -> 2 MIN : 25
4 -> 3 MIN : 19
4 -> 4 MIN : 0
4 -> 5 MIN : 13
4 -> 6 MIN : 21
4 -> 7 MIN : 9
5 -> 1 MIN : 11
5 -> 2 MIN : 12
5 -> 3 MIN : 6
5 -> 4 MIN : 13
5 -> 5 MIN : 0
5 -> 6 MIN : 8
5 -> 7 MIN : 17
6 -> 1 MIN : 3
6 -> 2 MIN : 7
6 -> 3 MIN : 2
6 -> 4 MIN : 21
6 -> 5 MIN : 8
6 -> 6 MIN : 0
6 -> 7 MIN : 13
7 -> 1 MIN : 16
7 -> 2 MIN : 20
7 -> 3 MIN : 11
7 -> 4 MIN : 9
7 -> 5 MIN : 17
7 -> 6 MIN : 13
7 -> 7 MIN : 0

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

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