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

79愛的鼓勵 1訂閱站台

作法 : SPFA

大概2秒多...算了

測資的點跟敘述不一樣啊  只開10001個!

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

#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000001
long long int min(long long int x,long long int y)
{
     if(x>=y) return y;
     else return x;
}
long long int input()     
{     
  char cha;     
  long long 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 ptime[10002]={0},SP[10002]={0};
long long int data[1000000][3],SUM;
short Queue[5000000];
int SPFA(int S,int N)  
{  
   long long int Dis[10002]={0};  
   int top=-1,a,b,c,used[10002]={0};  
   for(a=1;a<=N;a++)  
      Dis[a]=MAX;  
   for(a=SP[S],b=0;b<ptime[S];a++,b++)  
     {  
      Dis[data[a][1]]=min(Dis[data[a][1]],data[a][2]);  
      if(used[data[a][1]]==0)  
            Queue[++top]=data[a][1],used[data[a][1]]=1;  
     }  
   Dis[S]=0;  
   for(a=0;a<=top;a++)  
      {  
         int Qp=Queue[a];  
         used[Qp]=0;  
         for(b=SP[Qp],c=0;c<ptime[Qp];b++,c++)  
            if(Dis[data[b][1]]>Dis[Qp]+data[b][2])  
              {  
                 Dis[data[b][1]]=Dis[Qp]+data[b][2];  
                 if(used[data[b][1]]==0)  
                   Queue[++top]=data[b][1],used[data[b][1]]=1;  
              }
      }  
   if(S==1)
      for(a=2;a<=N;a++)
       SUM+=Dis[a];
   else
       SUM+=Dis[1];
   return 0;
}
int partition(int, int);   
void quicksort(int, int);
main()
{
  int N,M;
  while(scanf("%d %d",&M,&N)==2)
     {
        int a,b,c,d,x,y;
        for(a=0;a<N;a++)
           {
             x=input(),y=input(),d=input(); 
             data[a][0]=x,data[a][1]=y,data[a][2]=d;
             ptime[x]++;
           }
        quicksort(0,N-1);

        for(a=1;a<=M;a++)
            SP[a]=MAX;
        for(a=0;a<N;a++)
            SP[data[a][0]]=min(a,SP[data[a][0]]);       
        SUM=0;
        int Flag=0;
        for(a=1;a<=M;a++)
           Flag=SPFA(a,M);
        printf("%lld\n",SUM);
        for(a=1;a<=M;a++)
           ptime[a]=0;
     }
  return 0;
}
int partition(int left,int right)   
{  
  int a=left-1,b,s=data[right][0];  
  for(b=left;b<right;b++)  
   {  
     if(data[b][0]<s)  
       {  
         a++;  
         long long int temp;  
         temp=data[a][0];  
         data[a][0]=data[b][0];  
         data[b][0]=temp; 
         temp=data[a][1];  
         data[a][1]=data[b][1];  
         data[b][1]=temp;  
         temp=data[a][2];  
         data[a][2]=data[b][2];  
         data[b][2]=temp;
       }   
   }   
         long long int temp;  
         temp=data[a+1][0];  
         data[a+1][0]=data[right][0];  
         data[right][0]=temp;
         temp=data[a+1][1];  
         data[a+1][1]=data[right][1];  
         data[right][1]=temp;    
         temp=data[a+1][2];  
         data[a+1][2]=data[right][2];  
         data[right][2]=temp; 
   return a+1;   
}   
void quicksort(int left,int right)  
{  
 int q;  
 if(left<right)   
   {  
     q=partition(left,right);  
     quicksort(left,q-1);  
     quicksort(q+1,right);   
   }   
}