SPFA算法

提供两种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 <int> 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 <int> 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 }