讨论 / 为什么SPFA过不了这题?
zrp 2010-05-24 04:03:00
点我顶贴 收藏 删除
我是用SPFA做这题的,但是竟然总是只对1-2个点,其他点我的解比最优解大很多.

请大牛帮助~~谢谢

以下是我的源码

#include<stdio.h>

long map[2001][2001]={0};

long dui[100000]={0};

long f[2001]={0};

long hash[2001]={0};

long out[2001]={0};

long close=0,open=1;

long bushu[100000]={0};

main()

{

FILE *fp,*fo;

long i,j,k,l,m,n,v1,v2,pay,h,s,t,g,vi;

scanf("%ld%ld",&n,&m);

for(i=0;i<m;i++)

{

scanf("%ld%ld%ld",&v1,&v2,&pay);

map[v1][v2]=map[v2][v1]=pay;

}

s=1;

dui[0]=s;

hash[s]=1;

for(i=1;i<=n;i++)

if(i!=s)

f[i]=100000000;

while(close<open)

{

vi=dui[close];

for(i=1;i<=n;i++)

if(map[vi][i]!=0)

if(f[i]>f[vi]+map[vi][i]&&(bushu[close]!=1||i!=s))

{

f[i]=f[vi]+map[vi][i];

if(hash[i]==0)

dui[open++]=i;

hash[i]=1;

bushu[open-1]=bushu[close]+1;

}

hash[vi]=0;

if(close==0)

f[s]=10000000;

close++;

}

if(f[s]!=10000000)

printf("%ld",f[s]);

else

printf("He will never come back.");

// getch();

}

#1 小小小学生@2009-07-25 02:24:00
回复 删除
凄凉``帮你顶起。
#2 zrp@2009-07-25 18:29:00
回复 删除
...up
#3 zrp@2009-08-01 00:51:00
回复 删除
up...
#4 青龙白狐@2009-08-01 01:26:00
回复 删除
ms是最小环
#5 Aule@2009-08-01 05:04:00
回复 删除
这题是最小环,不用spfa
#6 zrp@2009-08-02 00:23:00
回复 删除
饿..是啊,我也知道..

但是为什么SPFA会错呢?..

#7 L.Lawliet@2010-05-24 04:03:00
回复 删除
[color=red]用dijkstra能不能过啊?[/color]
查看更多回复
提交回复