提供两种spfa算法模板

1.链表储存：

1 /*--------------------------spfa链表储存*/  2 const int N = 10100 ; 3  4 struct Edge{ 5     int to,w,nxt; 6 }e[100010]; 7 int head[N],p; 8 int dis[N]; 9 bool vis[N];10 queue 
     
       q;11 12 void spfa(int a)  //a点到其他点的最短距离 13 {14     memset(dis,0x3f,sizeof(dis));15     vis[a] = true;16     q.push(a);17     dis[a] = 0;18     while(!q.empty())19     {20         int d = q.front();21         for(int i = head[d]; i ;i = e[i].nxt)22         {23             int w = e[i].w ,v = e[i].to;24             if(dis[d] + w < dis[v])25             {26                 dis[v] = dis[d] + w;27                 if(!vis[v])28                 {29                     q.push(v);30                     vis[v] = true ; 31                 }32             }33         }34         q.pop();35         vis[d] = false ;36     }37 }
     

2.数组储存

1 /*----------------------------------spfa数组储存*/  2 const int N = 1010 ; 3 int map[N][N]; 4 int dis[N]; 5 bool vis[N]; 6 int n; 7 queue 
     
       q; 8  9 void spfa(int a)10 {11     memset(dis,0x3f,sizeof(dis));12     q.push(a);13     vis[a] = true;14     dis[a] = 0;15     while(!q.empty())16     {17         int d = q.front();18         for(int i=1;i<=n;++i)19         {20             if(map[d][i]!=0 && map[d][i]+dis[d] < dis[i])21             {22                 dis[i] = dis[d] + map[d][i];23                 if(!vis[i])24                 {25                     q.push(i);26                     vis[i] = true; 27                 }28             }29         }30         q.pop();31         vis[d] = false ;                                                                                                                                                                                                                                                                           32     }33 }