hiho一下 第二十五周（SPFA）

样例输入

5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63

样例输出

172

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <memory.h>
 4 #include <string>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <algorithm>
10 #include <climits>
11 using namespace std;
12 
13 #define MAXN 111111
14 #define MAX 1111111
15 struct node {
16     int x,weight;
17 };
18 vector< node > mp[MAXN];
19 int cost[MAX];  //存储到起始点的最近距离
20 int n,m,s,e;
21 
22 bool spfa()
23 {
24     queue<node> q;
25     cost[s] = 0;
26     q.push({s,0});
27     while (!q.empty())
28     {
29         node now = q.front();
30         q.pop();
31         if (cost[now.x] < now.weight) continue;
32         else cost[now.x] = now.weight;
33         for (int i = 0;i < mp[now.x].size();i++) {
34             //如果未访问过或者距离可更新
35             if (cost[mp[now.x][i].x] == -1 || cost[mp[now.x][i].x] > mp[now.x][i].weight + cost[now.x]) {
36                 cost[mp[now.x][i].x] = mp[now.x][i].weight + cost[now.x];                                
37                 q.push({mp[now.x][i].x,cost[mp[now.x][i].x]});
38             }
39 
40         }
41     }
42     return true;
43 }
44 
45 int main()
46 {
47     int a,b,w;
48     memset(cost,-1,sizeof(cost));    //权值为-1表示还未访问过
49     cin >> n >> m >> s >> e;
50     for (int i = 0;i < m; ++ i)  {
51         cin >> a >> b >> w;
52         mp[a].push_back({b,w});
53         mp[b].push_back({a,w});
54     }
55     if (spfa())
56     cout << cost[e] << endl;
57     return 0;
58 }

代码君

 

 

另外附上大牛的SFPA代码

 

SPFA的两种写法，bfs和dfs，bfs判别负环不稳定，相当于限深度搜索，但是设置得好的话还是没问题的，dfs的话判断负环很快

 1 int spfa_bfs(int s)
 2 {
 3     queue <int> q;
 4     memset(d,0x3f,sizeof(d));
 5     d[s]=0;
 6     memset(c,0,sizeof(c));
 7     memset(vis,0,sizeof(vis));
 8 
 9     q.push(s);  vis[s]=1; c[s]=1;
10     //顶点入队vis要做标记，另外要统计顶点的入队次数
11     int OK=1;
12     while(!q.empty())
13     {
14         int x;
15         x=q.front(); q.pop();  vis[x]=0;
16         //队头元素出队，并且消除标记
17         for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
18         {
19             int y=v[k];
20             if( d[x]+w[k] < d[y])
21             {
22                 d[y]=d[x]+w[k];  //松弛
23                 if(!vis[y])  //顶点y不在队内
24                 {
25                     vis[y]=1;    //标记
26                     c[y]++;      //统计次数
27                     q.push(y);   //入队
28                     if(c[y]>NN)  //超过入队次数上限，说明有负环
29                         return OK=0;
30                 }
31             }
32         }
33     }
34 
35     return OK;
36 
37 }

BFS

 

 1 int spfa_dfs(int u)
 2 {
 3     vis[u]=1;
 4     for(int k=f[u]; k!=0; k=e[k].next)
 5     {
 6         int v=e[k].v,w=e[k].w;
 7         if( d[u]+w < d[v] )
 8         {
 9             d[v]=d[u]+w;
10             if(!vis[v])
11             {
12                 if(spfa_dfs(v))
13                     return 1;
14             }
15             else
16                 return 1;
17         }
18     }
19     vis[u]=0;
20     return 0;
21 }

DFS

 

hiho一下 第二十五周（SPFA）

原文：http://www.cnblogs.com/usedrosee/p/4185793.html