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

79愛的鼓勵 1訂閱站台

作法 : SPFA

之前所寫的方法是原創的,所以不確定其演算法的正確性!

以下的,用SPFA寫的,再加上優化輸入  所以才可以達到極致

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

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000000
int map[1001][300][2]={0};
int N,M,S,E;
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;  
}
int min(int x,int y)  
{  
     if(x>=y) return y;  
     else return x;  
}
int max(int x,int y)  
{  
     if(x>=y) return x;  
     else return y;  
}
short Queue[5000000],maptop[1001]={0};
int SPFA(int S,int N,int E)     
{     
   int Dis[1001]={0},a,b,c,used[1001]={0};     
   int top=-1;     
   Dis[S]=MAX;
   for(a=0;a<maptop[S];a++)     
     {     
      Dis[map[S][a][0]]=max(Dis[map[S][a][0]],map[S][a][1]);     
      if(used[map[S][a][0]]==0)
            Queue[++top]=map[S][a][0],used[map[S][a][0]]=1;     
     }     
   for(a=0;a<=top;a++)     
      {     
         int Qp=Queue[a];     
         used[Qp]=0;          
         for(b=0;b<maptop[Qp];b++)     
            {
              int R=min(Dis[Qp],map[Qp][b][1]);
              if(Dis[map[Qp][b][0]]<R)
                {     
                   Dis[map[Qp][b][0]]=R;     
                   if(used[map[Qp][b][0]]==0)     
                     Queue[++top]=map[Qp][b][0],used[map[Qp][b][0]]=1;     
               }     
            }
      }     
   printf("%d\n",Dis[E]);
}    
main()
{
 while(scanf("%d %d",&N,&M)==2&&N)
    {
       int a,b,c,x,y,data;
       for(a=0;a<M;a++)
         {
           x=input(),y=input(),data=input();
           map[x][maptop[x]][0]=y;
           map[x][maptop[x]++][1]=data;
           map[y][maptop[y]][0]=x;
           map[y][maptop[y]++][1]=data;
         }
        scanf("%d %d",&S,&E);
        SPFA(S,N,E);
        for(a=1;a<=N;a++)   maptop[a]=0; 
  }
 return 0;
}