spfa.cpp

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 从名字我们就可以看出

#include    <iostream>
#include    <deque>
using      namespace     std;
const      int      MaxN = 10000 + 1;
deque      <int>    P;
struct     map
{
           int    data , len;
           map *  next;           
};
map        *     h[MaxN];
int        N , S , T , dist[MaxN];
bool       flag[MaxN];
void       Insert(int  x , int y , int l)
{
           map * temp;
           temp = new   map;
           temp -> data = y;
           temp -> len =  l;
           temp -> next = h[x];
           h[x]  = temp;           
}
void       Input()
{
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
           scanf("%d%d%d",&N,&S,&T);
           int     a , b ,  c , i;
           P.push_front(S);
           flag[S] = true;
           for (i = 1 ; i <= N ; i++)
           {
                 scanf( "%d%d%d" , &a , &b ,&c);
                 Insert(a , b , c);
                 Insert(b , a , c);    
           }           
}
void       SPFA()
{
           int    k;
           map    * temp;
           memset(dist , 125 , sizeof(dist));
           dist[S] = 0;
           while (!P.empty())
           {
                    k = P.front();
                    P.pop_front();
                    temp = h[k];
                    flag[k] = false;
                    while(temp != NULL)
                    {
                           if (dist[k] + temp-> len < dist[temp -> data] )  
                           {
                                     dist[temp -> data] =   dist[k] + temp-> len;
                                     if (!flag[temp -> data])
                                     {
                                              P.push_back(temp -> data);
                                              flag[temp -> data] = true;
                                     }
                           }        
                           temp = temp -> next;
                    }                   
           }           
}
void       Output()
{
           printf("%d\n",dist[T]);           
}
int        main()
{
           Input();
           SPFA();
           Output();
           return 0;           
}