SPFA模板

Spfa是一种求单源最短路径的算法,时间复杂度为O(每个节点进队次数*边数);(然而对这个复杂度并不是很有概念,比堆优dij是快还是慢啊。。。)

算法流程:

  1. dis数组表示源点s到各点的距离,初始化dis[]={inf}; dis[s]=0;
  2. 源点进队;
  3. 队首出队;
  4. 对队首的每个邻接点做松弛操作;
  5. 对于每个被松弛的点,若不在队列中,则加入队列;
  6. 重复3~5至队列为空,此时的dis为最短路;
  7. STL的queue真是个好东西。
     1 void spfa(int k){
     2     int i;
     3     memset(dis,127,sizeof(dis));
     4     memset(b,0,sizeof(b));
     5     q.push(k);//源点入队
     6     b[k]=true;
     7     dis[k]=0;
     8     while(!q.empty()){
     9         k=q.front();
    10         q.pop();//记录队首并弹出
    11         b[k]=false;//撤销入队标记
    12         for(i=head[k];i!=-1;i=e[i].next){
    13             if(dis[e[i].to]>dis[k]+e[i].w){//若可以松弛
    14                 dis[e[i].to]=dis[k]+e[i].w;//更新距离
    15                 if(!b[e[i].to]){
    16                     q.push(e[i].to);//入队
    17                     b[e[i].to]=true;//标记已入队
    18                 }
    19             }
    20         }
    21     }
    22 }

例题:

Codevs2038香甜的黄油

对于每个点求一次spfa单元最短路,保留最小值作为答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 
 8 struct edge{
 9     int to;
10     int w;
11     int next;
12 };
13 queue<int> q;
14 edge e[10000];
15 int ne=0,head[1000],dis[1000],a[1000];
16 bool b[1000];
17 void add(int a,int b,int c){
18     e[++ne].to=b;e[ne].w=c;e[ne].next=head[a];head[a]=ne;
19 }
20 
21 void spfa(int k){
22     int i;
23     memset(dis,127,sizeof(dis));
24     memset(b,0,sizeof(b));
25     q.push(k);//源点入队
26     b[k]=true;
27     dis[k]=0;
28     while(!q.empty()){
29         k=q.front();
30         q.pop();//记录队首并弹出
31         b[k]=false;//撤销入队标记
32         for(i=head[k];i!=-1;i=e[i].next){
33             if(dis[e[i].to]>dis[k]+e[i].w){//若可以松弛
34                 dis[e[i].to]=dis[k]+e[i].w;//更新距离
35                 if(!b[e[i].to]){
36                     q.push(e[i].to);//入队
37                     b[e[i].to]=true;//标记已入队
38                 }
39             }
40         }
41     }
42 }
43 
44 int main(){
45     int n,p,c,ans=999999999,i,j,u,v,w;
46     memset(head,-1,sizeof(head));
47     memset(e,0,sizeof(e));
48     scanf("%d%d%d",&n,&p,&c);
49     for(i=1;i<=n;i++)scanf("%d",&a[i]);
50     for(i=1;i<=c;i++){
51         scanf("%d%d%d",&u,&v,&w);
52         add(u,v,w);
53         add(v,u,w);//前向星连边
54     }
55     for(i=1;i<=p;i++){
56         spfa(i);
57         int sum=0;
58         for(j=1;j<=n;j++)sum+=dis[a[j]];
59         ans=min(ans,sum);
60     }
61     printf("%d
",ans);
62 }
【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/y-m-y/p/5719894.html