题目题解代码

题目

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

题解

spfa跑一遍，然后输出 做错的原因主要在于对spfa的不熟悉 这里放一个标准spfa（储存格式为链表）

链表例子：

数据 x y w//从x到y要w 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 ls 1 2 3 4 5 //点1——5 4 3 5 4 0 //点i最后一次在g中的位置 g 1 2 3 4 5 6 //6条边 x 1 2 2 1 3 1 y 2 3 4 3 4 4 w 2 2 1 5 3 4 next 0 0 2 1 0 0 //点i上一次在g中的位置 procedure spfa; var head,tail,t:longint; begin head:=0; tail:=1; list[1]:=1;//起始点入队 v[1]:=1; //初始时把起始点先放进队列里 while head<>tail do//与广搜类似 begin head:=head+1; t:=ls[list[head]]; while t>0 do with g[t] do//记录类型，下面的程序里x=g[t].x,y=g[t].y,w=g[t].w begin if d[x]+w<d[y] then //松弛操作 begin d[y]:=d[x]+w; if v[y]=0 then //新的点未松弛但被更新了d值 begin v[y]:=1;//入队 tail:=tail+1;//尾指针加一 list[tail]:=y;//入队 end; end; t:=next; end; v[list[head]]:=0;//该点移出队列 end; end;

代码

type rec=record x,y,w,ne:longint; end; var n,m,s,i,j:longint; a:array[1..500000]of rec; d,ls,v:array[0..10000]of longint; state:array[1..500000]of longint; procedure spfa; var h,t,i,x,y,w,ne:longint; begin h:=0;t:=1; d[s]:=0;state[1]:=s;v[s]:=1; while h<t do begin inc(h); i:=ls[state[h]]; while i>0 do begin x:=a[i].x;y:=a[i].y;w:=a[i].w;ne:=a[i].ne; if d[x]+w<d[y] then begin d[y]:=d[x]+w; if v[y]=0 then begin v[y]:=1; inc(t); state[t]:=y; end; end; i:=ne; end; v[state[h]]:=0; end; end; begin readln(n,m,s); for i:=1 to m do begin readln(a[i].x,a[i].y,a[i].w); a[i].ne:=ls[a[i].x]; ls[a[i].x]:=i; end; fillchar(d,sizeof(d),$7f); spfa; for i:=1 to n do if d[i]=d[0] then write('2147483647 ') else if i=s then write('0 ') else write(d[i],' '); end.