作法 : 仍是SPFA

但是為了不使用內建與鏈結串鏈  當初使用快排去做排序

後來發現  若使用merge sort會比較穩定

可能是快排退化了吧...

速度達到極致 8ms 不用case第五筆

順便也做出了

"

若所給通道資料無法由
侍衛休息室通到某一間房間，請輸出0。

                          "

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

#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000001
int min(int x,int y)
{
     if(x>=y) return y;
     else return x;
}
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 ptime[10002]={0},SP[10002]={0};
int data[1000000][3];
long long SUM;
short Queue[5000000];
int SPFA(int S,int N)  
{  
   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;  
              }
      }  
      for(a=1;a<=N;a++)
        if(Dis[a]==MAX)  return 1;
        else   SUM+=Dis[a];
   return 0;
}
int MergeSort(int,int);
int Merge(int,int,int);
main()
{
  int N,M;
  while(scanf("%d %d",&M,&N)==2)
     {
        int a,b,c,d,x,y,Flag=0;
        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]++;
           }
        MergeSort(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;
        Flag=SPFA(1,M);
        for(a=1;a<=M;a++)    SP[a]=MAX,ptime[a]=0;
        for(a=0;a<N;a++)
            b=data[a][0],data[a][0]=data[a][1],data[a][1]=b,ptime[data[a][0]]++;
        if(Flag==1) {printf("0\n");continue;}
        MergeSort(0,N-1);
        for(a=0;a<N;a++)
            SP[data[a][0]]=min(a,SP[data[a][0]]);
       
        Flag=SPFA(1,M);
        if(Flag==1) printf("0\n");
        else
            printf("%lld\n",SUM);
        for(a=1;a<=M;a++)
           ptime[a]=0;
     }
  return 0;
}
int MergeSort(int l,int h)
{
   if(l<h)
      {
         int m=(l+h)/2;
         MergeSort(l,m);
         MergeSort(m+1,h);
         Merge(l,m,h);
      }
}
int x[100001][3];
int Merge(int l,int m,int h)
{
   int in1=l,in2=m+1,out=l;
   int top=0,a,b;
   while(in1<=m&&in2<=h)
      if(data[in1][0]>data[in2][0])
           x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
      else
           x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in1<=m)
       x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in2<=h)
       x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
   for(a=l,b=0;a<=h;a++,b++)
      data[a][0]=x[b][0],data[a][1]=x[b][1],data[a][2]=x[b][2];
}
/*
3 9
1 1 8
2 3 47
2 1 42
2 2 24
2 1 5
2 2 3
3 1 46
3 1 15
2 3 24
*/