输入样例:
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(使用了边集数组!): - /* Author: Hahahuo
- * Date: 10,11,2011
- * City: Wuhan
- * Website: www.ahalei.com
- * Title: SPFA (Shortest Path Faster Algorithm)
- * Tips: 1.SPFA算法是西南交通大学段凡丁于1994年发表的。
- * 2.小提示:个人认为,ahalei画的图非常好,数据也很好。
- * 为什么呢?因为M≠N。大家调试的时候,第一件事,就是检查M和N是否写反了。
- * 去年NOIP时候,我就是因为这件事浪费了非常多的时间。现在大部分测试中,图论题一定给的是N=M!
- * (这是出题的技巧!)
- */
- #include<cstdio>
- #include<iostream>
- #include<queue>//C++_STL 标准模板库
- #define MAXN 100+1
- #define MAXM 100+1
- using namespace std;
- int n,m;
- int dis[MAXN];
- bool book[MAXN];
- struct edge//边
- {
- int start;
- int end;
- int length;
- }map[MAXM];//边集数组,将时间复杂度降至O(2M)
- struct point
- {
- int start;
- int end;
- }points_to_edges[MAXN];//表示以某个点为起点的边 是从第几号边 到第几号边
- int cmp(const void *x,const void *y)
- {
- return (*(edge *)x).start - (*(edge *)y).start;
- }//small to big
- void input()
- {
- scanf("%d %d",&n,&m);
- for(int i=1;i<=m;i++)
- scanf("%d %d %d",&map.start,&map.end,&map.length);
- return;
- }
- void output()
- {
- for(int i=1;i<=n;i++)
- printf("%d ",dis);
- printf("\n");
- return;
- }
- void init_map()
- {
- qsort(&map[1],m,sizeof(map[0]),cmp);
- for(int i=1;i<=m;i++)
- {
- if(map.start!=map[i-1].start)
- points_to_edges[ map.start ].start = i;
- if(map.start!=map[i+1].start)
- points_to_edges[ map.start ].end = i;
- }//构建数组
- return;
- }
- void spfa()
- {
- for(int i=2;i<=n;i++)
- dis=2000000000;
- queue <int> que;
- book[1]=true;//每次查找一遍是否在队中,非常浪费时间复杂度。
- que.push(1);//将第一个点入队
- while(!que.empty())
- {
- int cur = que.front();
- for(int i=points_to_edges[ cur ].start; i<=points_to_edges[ cur ].end; i++)
- if(dis[ map.end ] > dis[cur] + map.length)
- {
- dis[ map.end ] = dis[cur] + map.length;//松弛成功
- if(!book)//该点不在队中,则入队
- {
- book=true;
- que.push(i);
- }
- }
- book[cur]=false;//出队
- que.pop();
- }
- }
- int main()
- {
- input();
- init_map();
- spfa();
- output();
- return 0;
- }
复制代码
代码2(普通版太阳型spfa):
- // Author: Ahalei
- // Date: 11 1, 2010
- // City: Wuhan
- // Website: www.ahalei.com
- // Title: SPFA (Shortest Path Faster Algorithm)
- // Tips: SPFA算法是西南交通大学段凡丁于1994年发表的
- #include <stdio.h>
- #define MAX 999
- int main()
- {
- //文件输入输出
- freopen("spfa.in","r",stdin);
- freopen("spfa.out","w",stdout);
- //
- int E[6][6]={0},dis[6]={0},book[6]={0};
- int que[11]={0},top,bottom;
- int i,j,n,m,x,y,cur;
- scanf("%d %d",&n,&m);
- //初始化边的关系,这里很重要,否则会出错
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- {
- if(i==j)
- E[j]=0;
- else
- E[j]=MAX;
- }
- //读入边
- for(i=1;i<=m;i++)
- {
- scanf("%d %d",&x,&y);
- scanf("%d",&E[x][y]);
- }
- //1号顶点到其余各定点的距离的初始化
- dis[1]=0;
- for(i=2;i<=n;i++)
- {
- dis=MAX;
- }
- //队列初始化
- top=1;
- bottom=0;
- //1号顶点入队
- bottom++;
- que[bottom]=1;
- //标记1号顶点已经入队
- book[1]=1;
- while(top<=bottom)
- {
- //当前需要扩展的顶点
- cur=que[top];
- //扫描当前顶点所有的边
- for(i=1;i<=n;i++)
- {
- //dis表示1号顶点到第i号顶点的距离
- //dis[cur]表示1号顶点到当前队列中top指向的顶点顶点(也就是当前正在扩展的顶点)的距离
- //E[cur]表示当前顶点到i号顶点的距离
- if(E[cur]!=MAX)//如果cur和i两个节点之间有边的情况下
- {
- if(dis>dis[cur]+E[cur])
- {
- //如果1号顶点到当前顶点的距离 >当前顶点的距离+当前顶点到i号顶点的距离
- //说明1号顶点到 i顶点 的距离,通过当前顶点(cur)到i顶点这条边 ,距离被减少了。这里称作松弛成功。
- dis=dis[cur]+E[cur];//更新 1号顶点到 i顶点 的距离
- if(book==0)//这的book数组用来判断i号顶点是否在队列中,否则每次都从队列的top到bottom扫描一遍太麻烦了。
- {
- //为0表示不在队列中,则将i号顶点加入到队列里。
- //下面两句是入队操作
- bottom++;
- que[bottom]=i;
- //同时标记i号顶点已经入队
- book=1;
- }
- }
- }
- }
- //当前顶点出队
- book[cur]=0;//标记当前顶点出队
- //出队操作
- top++;
- }
- //输出i号顶点到其余各个顶点的距离
- for(i=1;i<=n;i++)
- printf("%d ",dis);
- return 0;
- }
复制代码
|