[图论]一个叫做SPFA的东西(已更新)

啊哈磊

输入样例：
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6

输出样例：
0 2 5 9 9

代码1（使用了边集数组！）：

1. /* Author: Hahahuo
   
2. * Date: 10,11,2011
   
3. * City: Wuhan
   
4. * Website: www.ahalei.com
   
5. * Title: SPFA (Shortest Path Faster Algorithm)
   
6. * Tips: 1.SPFA算法是西南交通大学段凡丁于1994年发表的。
   
7. *       2.小提示：个人认为，ahalei画的图非常好，数据也很好。
   
8. *                 为什么呢？因为M≠N。大家调试的时候，第一件事，就是检查M和N是否写反了。
   
9. *                           去年NOIP时候，我就是因为这件事浪费了非常多的时间。现在大部分测试中，图论题一定给的是N=M！
   
10. *                           （这是出题的技巧！）
    
11. */
    
12. #include<cstdio>
    
13. #include<iostream>
    
14. #include<queue>//C++_STL 标准模板库
    
15. #define MAXN 100+1
    
16. #define MAXM 100+1
    
17. using namespace std;
    
18. int n,m;
    
19. int dis[MAXN];
    
20. bool book[MAXN];
    
21. struct edge//边
    
22. {
    
23.         int start;
    
24.         int end;
    
25.         int length;
    
26. }map[MAXM];//边集数组，将时间复杂度降至O(2M)
    
27. struct point
    
28. {
    
29.         int start;
    
30.         int end;
    
31. }points_to_edges[MAXN];//表示以某个点为起点的边 是从第几号边 到第几号边
    
32. int cmp(const void *x,const void *y)
    
33. {
    
34.         return (*(edge *)x).start - (*(edge *)y).start;
    
35. }//small to big
    
36. void input()
    
37. {
    
38.         scanf("%d %d",&n,&m);
    
39.         for(int i=1;i<=m;i++)
    
40.                 scanf("%d %d %d",&map.start,&map.end,&map.length);
    
41.         return;
    
42. }
    
43. void output()
    
44. {
    
45.         for(int i=1;i<=n;i++)
    
46.                 printf("%d ",dis);
    
47.         printf("\n");
    
48.         return;
    
49. }
    
50. void init_map()
    
51. {
    
52.         qsort(&map[1],m,sizeof(map[0]),cmp);
    
53.         for(int i=1;i<=m;i++)
    
54.         {
    
55.                 if(map.start!=map[i-1].start)
    
56.                         points_to_edges[ map.start ].start = i;
    
57.                 if(map.start!=map[i+1].start)
    
58.                         points_to_edges[ map.start ].end = i;
    
59.         }//构建数组
    
60.         return;
    
61. }
    
62. void spfa()
    
63. {
    
64.         for(int i=2;i<=n;i++)
    
65.                 dis=2000000000;
    
66.         queue <int> que;
    
67.         book[1]=true;//每次查找一遍是否在队中，非常浪费时间复杂度。
    
68.         que.push(1);//将第一个点入队
    
69.         while(!que.empty())
    
70.         {
    
71.                 int cur = que.front();
    
72.                 for(int i=points_to_edges[ cur ].start; i<=points_to_edges[ cur ].end; i++)
    
73.                         if(dis[ map.end ] > dis[cur] + map.length)
    
74.                         {
    
75.                                 dis[ map.end ] = dis[cur] + map.length;//松弛成功
    
76.                                 if(!book)//该点不在队中，则入队
    
77.                                 {
    
78.                                         book=true;
    
79.                                         que.push(i);
    
80.                                 }
    
81.                         }
    
82.                 book[cur]=false;//出队
    
83.                 que.pop();
    
84.          }
    
85. }
    
86. int main()
    
87. {
    
88.         input();
    
89.         init_map();
    
90.         spfa();
    
91.         output();
    
92.         return 0;
    
93. }

复制代码

代码2(普通版太阳型spfa)：

1. // Author: Ahalei
   
2. // Date: 11 1, 2010
   
3. // City: Wuhan
   
4. // Website: www.ahalei.com
   
5. // Title: SPFA (Shortest Path Faster Algorithm)
   
6. // Tips: SPFA算法是西南交通大学段凡丁于1994年发表的
   
7. 
   
8. #include <stdio.h>
   
9. #define MAX 999
   
10. int main()
    
11. {
    
12.     //文件输入输出
    
13.     freopen("spfa.in","r",stdin);
    
14.     freopen("spfa.out","w",stdout);
    
15.     //
    
16.     int E[6][6]={0},dis[6]={0},book[6]={0};
    
17.     int que[11]={0},top,bottom;
    
18.     int i,j,n,m,x,y,cur;
    
19. 
    
20.     scanf("%d %d",&n,&m);
    
21. 
    
22.     //初始化边的关系，这里很重要，否则会出错
    
23.     for(i=1;i<=n;i++)
    
24.         for(j=1;j<=n;j++)
    
25.         {
    
26.             if(i==j)
    
27.                 E[j]=0;
    
28.             else
    
29.                 E[j]=MAX;
    
30.         }
    
31. 
    
32.     //读入边   
    
33.     for(i=1;i<=m;i++)
    
34.     {
    
35.         scanf("%d %d",&x,&y);
    
36.         scanf("%d",&E[x][y]);      
    
37.     }
    
38. 
    
39.     //1号顶点到其余各定点的距离的初始化
    
40.     dis[1]=0;
    
41.     for(i=2;i<=n;i++)
    
42.     {
    
43.         dis=MAX;
    
44.     }
    
45.     //队列初始化
    
46.     top=1;
    
47.     bottom=0;
    
48.     //1号顶点入队
    
49.     bottom++;
    
50.     que[bottom]=1;
    
51.     //标记1号顶点已经入队
    
52.     book[1]=1;
    
53.     while(top<=bottom)
    
54.     {
    
55.         //当前需要扩展的顶点
    
56.         cur=que[top];
    
57.         //扫描当前顶点所有的边
    
58.         for(i=1;i<=n;i++)
    
59.         {
    
60.             //dis表示1号顶点到第i号顶点的距离
    
61.             //dis[cur]表示1号顶点到当前队列中top指向的顶点顶点(也就是当前正在扩展的顶点)的距离
    
62.             //E[cur]表示当前顶点到i号顶点的距离
    
63.             if(E[cur]!=MAX)//如果cur和i两个节点之间有边的情况下
    
64.             {
    
65.                 if(dis>dis[cur]+E[cur])
    
66.                 {
    
67.                     //如果1号顶点到当前顶点的距离 >当前顶点的距离+当前顶点到i号顶点的距离
    
68.                     //说明1号顶点到 i顶点 的距离，通过当前顶点(cur)到i顶点这条边 ，距离被减少了。这里称作松弛成功。
    
69.                     dis=dis[cur]+E[cur];//更新 1号顶点到 i顶点 的距离
    
70.                     if(book==0)//这的book数组用来判断i号顶点是否在队列中，否则每次都从队列的top到bottom扫描一遍太麻烦了。
    
71.                     {
    
72.                         //为0表示不在队列中，则将i号顶点加入到队列里。
    
73.                         //下面两句是入队操作
    
74.                         bottom++;
    
75.                         que[bottom]=i;
    
76.                         //同时标记i号顶点已经入队
    
77.                         book=1;
    
78.                     }  
    
79.                 }
    
80.             }
    
81.         }
    
82.         //当前顶点出队
    
83.         book[cur]=0;//标记当前顶点出队
    
84.         //出队操作
    
85.         top++;   
    
86.     }
    
87. 
    
88.     //输出i号顶点到其余各个顶点的距离
    
89.     for(i=1;i<=n;i++)
    
90.         printf("%d ",dis);
    
91. 
    
92.     return 0;
    
93. }

复制代码

55行和57行有问题吧