SPFA

ゝ一纸荒年。 2021-11-29 04:42 228阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<algorithm>
     3 #include<cstdio>
     4 #include<cstring>
     5 #include<queue>
     6 using namespace std;
     7 const int MAX_V = 1100;
     8 const int MAX_E = 110000;
     9 const int INF = 0x3f3f3f3f;
    10 
    11 struct ENode
    12 {
    13     int to;
    14     int w;
    15     int Next;
    16 };
    17 ENode edegs[MAX_E];
    18 int Head[MAX_V], tnt;
    19 void Add_ENode (int a, int b, int w)
    20 {
    21     ++ tnt;
    22     edegs[tnt].to= b;
    23     edegs[tnt].w= w;
    24     edegs[tnt].Next= Head[a];
    25     Head[a]= tnt;
    26     ++ tnt;
    27     edegs[tnt].to= a;
    28     edegs[tnt].w= w;
    29     edegs[tnt].Next= Head[b];
    30     Head[b]= tnt;
    31 }
    32 
    33 int Dis[MAX_V];
    34 bool visit[MAX_V]; //是否已经遍历过;
    35 int que[MAX_V]; // 模拟队列;
    36 int outque[MAX_V]; //记录每个点出队列的次数，防止有负边，保证无负边的图可以省略;
    37 bool SPFA(int s, int n)
    38 {
    39     /*s：起点； n：点的总数*/
    40     int iq; //队列中元素个数;
    41     memset(Dis, INF, sizeof(Dis));
    42     memset(visit, false, sizeof(visit));
    43     memset(outque, 0, sizeof(outque));
    44     iq= 0;
    45     que[iq ++]= s;
    46     visit[s]= true;
    47     Dis[s]= 0;
    48     int i= 0;
    49     while (i< iq)
    50     {
    51         int u= que[i];
    52         visit[u]= false;
    53         outque[u] ++;
    54         if (outque[u]> n) return false; //当一个点进出队列超过n 次，必然有负边存在;
    55 
    56         for (int k= Head[u]; k!= -1; k= edegs[k].Next)
    57         {
    58             /*bfs,和Dijkstra相似*/
    59             int v= edegs[k].to;
    60             if (Dis[v]> Dis[u]+ edegs[k].w)
    61             {
    62                 Dis[v]= Dis[u]+ edegs[k].w;
    63                 if (! visit[v])
    64                 {
    65                     visit[v]= true;
    66                     que[iq ++]= v;
    67                 }
    68             }
    69         }
    70         i ++;
    71     }
    72     return true;
    73 }
    74 
    75 void into()
    76 {
    77     /**初始化*/
    78     memset(Head,-1,sizeof(Head));
    79     tnt= -1;
    80 }
    81 
    82 int main()
    83 {
    84     int n, m;
    85     int a, b, w;
    86     while (~ scanf("%d %d", &n, &m))
    87     {
    88         into();
    89         for (int i= 0; i< m; i ++)
    90         {
    91             scanf("%d %d %d", &a, &b, &w);
    92             Add_ENode(a, b, w);
    93         }
    94         SPFA(1, n);
    95         printf("%d\n", Dis[n]);
    96     }
    97     return 0;
    98 }

转载于:https://www.cnblogs.com/Amaris-diana/p/11205557.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/c99036a36e1b427d93a50207e5a0f2d0.png