SPFA

左手的ㄟ右手 2021-10-25 13:54 212阅读 0赞

## 最坏情况下时间复杂度：O(nm) ##

## 一般情况下时间复杂度优于Bellman Ford ##

1 #include<iostream>
     2 #include<algorithm>
     3 #include<string.h>
     4 #include<cstdio>
     5 #include<queue>
     6 using namespace std;
     7 struct edge
     8 {
     9     int to;
    10     int weight;
    11     int next;
    12 }e[2002*2002*4];
    13 int head[3003];
    14 int dis[3003];
    15 int vis[3003];
    16 int cnt[3003];
    17 int n,m;
    18 int tot;
    19 bool spfa(int s)
    20 {
    21     queue<int> q;
    22     memset(dis,0x3f3f3f3f,sizeof(dis));
    23     memset(vis,0,sizeof(vis));
    24     memset(cnt,0,sizeof(cnt));
    25     dis[s]=0;
    26     vis[s]=1;
    27     q.push(s);
    28     while(!q.empty())
    29     {
    30         int u=q.front();
    31         q.pop();
    32         vis[u]=0;
    33         for(int i=head[u];i;i=e[i].next)
    34         {
    35             int to=e[i].to;
    36             if(dis[u]<0x3f3f3f3f&&dis[to]>dis[u]+e[i].weight)
    37             {
    38                 dis[to]=dis[u]+e[i].weight;
    39                 if(!vis[to])
    40                 {
    41                     q.push(to);
    42                     vis[to]=1;
    43                     if(++cnt[to]>n)
    44                     return 0;
    45                 }
    46             }
    47         }
    48     }
    49     return 1;
    50 }
    51 void add(int x,int y,int z)
    52 {
    53     tot++;
    54     e[tot].to=y;
    55     e[tot].weight=z;
    56     e[tot].next=head[x];
    57     head[x]=tot;
    58 }
    59 int main()
    60 {
    61     cin>>n>>m;
    62     for(int i=1;i<=m;i++)
    63     {
    64         int x,y,z;
    65         cin>>x>>y>>z;
    66         add(x,y,z);
    67         add(y,x,z);
    68     }
    69     spfa(1);
    70     cout<<dis[n]<<endl;
    71     return 0;
    72 }

转载于:https://www.cnblogs.com/HNFOX/p/11306223.html