讨论 / shortest为什么会错成这样
谧芒 2012-10-30 16:41:00
点我顶贴 收藏 删除
按照我的思路,用模拟数组链表+spfa,每次找到更短的路经就更新,同时更新步数,或者在路径长度相同时更新步数,这样做一组都不过,甚至连最短路后四组都挂了。

诸位大牛帮帮我啊!!!!

这是我悲催的程序

program aa;

var

last:array[1..50000] of longint;

dis:array[1..50000] of qword;

outt,cost,pre:array[1..300000] of longint;

n,m,a,b,i,c,min,sum:longint;

q:array[1..300000] of record

data,step:longint;

end;

procedure spfa;

var

h,t,k,v:longint;

begin

fillchar(dis,sizeof(dis),$3f);

h:=0;

t:=1;

q[1].data:=1;

dis[1]:=0;

min:=maxlongint;

while h<t do

begin

inc(h);

v:=q[h].data;

k:=last[v];

while k<>0 do

begin

if dis[v]+cost[k]<dis[outt[k]] then

begin

dis[outt[k]]:=dis[v]+cost[k];

inc(t);

q[t].data:=outt[k];

q[t].step:=q[h].step+1;

if q[t].data=n then

ifq[t].step<min then min:=q[t].step;

end;

k:=pre[k];

end;

end;

end;

procedure add(a,b,c:longint);

begin

inc(sum);

outt[sum]:=b;

cost[sum]:=c;

pre[sum]:=last[a];

last[a]:=sum;

end;

begin

readln(n,m);

for i:=1to m do

begin

read(a,b,c);

add(a,b,c);

add(b,a,c);

end;

min:=maxlongint;

spfa;

writeln(dis[n],' ',min);

end.

#1 blackbbc@2012-10-28 19:28:00
回复 删除
SPFA过不了 不用试了 = =

我用SPFA跑了5组 真心受不了

貌似 只能用地杰斯特拉 过

#2 谧芒@2012-10-30 16:41:00
回复 删除
谢谢了。我用SPFA过了七组

RT,还得学heap

查看更多回复
提交回复