Pascal问题
10^5那么小,广度优先遍历.
----13.1.21 upgrade------
本来不想写的,看到那位大哥说dp,实在觉得不贴对不起我这回答.
好吧说bfs算是我敷衍了.这个其实是spfa.这题其实可以看成图论.
var k,t,x,y,head,tail:longint;
queue,distant:array[1..100010]of longint;
hash:array[1..100010]of boolean;
begin
for i:=1 to 100010 do
distant[i]:=1000000;
readln(x,y);
distant[x]:=0;
queue[1]:=x;
hash[x]:=true;
head:=0;
tail:=1;
repeat
inc(head);
hash[head]:=false;
k:=distant[queue[head]];
if(queue[head]=y)then begin
writeln(k);
break;
end;
if(queue[head]>1)then begin
t:=queue[head]-1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
if(queue[head]<100000)then begin
t:=queue[head]+1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
if(queue[head]shl 1<=100000)then begin
t:=queue[head]shl 1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
until head=tail;
end.
pascal语言 最短路径 程序
program SPFA1(input,output);
var
used:array[1..100] of boolean;
line,len:array[1..100] of longint;
flat:array[1..100,1..100] of longint;
i,n,a,b:longint;
procedure SPFA(s:longint);
var
f,r,k:longint;
begin
f:=1;
r:=1;
line[f]:=s;
used[s]:=true;
for i:=1 to n do len[i]:=maxlongint;
len[s]:=0;
while f<=r do
begin
k:=line[f];
for i:=1 to n do
if len[i]>flat[k,i]+len[k] then
begin
len[i]:=flat[k,i]+len[k];
if used[i]=false then
begin
used[i]:=true;
inc(r);
line[r]:=k;
end;
end;
used[k]:=false;
inc(f);
end;
end;
begin
//assign(input,'SPFA.in');reset(input);
//assign(output,'SPFA.out');rewrite(output);
readln(n);
for i:=1 to n do
readln(a,b,flat[a,b]);
SPFA(4);
writeln(len[n]);
close(input);
close(output);
end.
这是SPFA，请采纳谢谢。
spfa能够解决什么样的问题？能够解决没有负权的回路吗？谢谢
spfa 可以有负权，但求最短路时不能有负权回路，最长路时不能有正权回路
适用条件&范围
l 单源最短路径(从源点s到其它所有顶点v);
l 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
l 边权可正可负(如有负权回路输出错误提示);
l 差分约束系统（需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，=构图时类似）。
负环处理
需要特别注意的是：仅当图不存在负权回路时，SPFA能正常工作。如果图存在负权回路，由于负权回路上的顶点无法收敛，总有顶点在入队和出队往返，队列无法为空，这种情况下SPFA无法正常结束。
判断负权回路的方案很多，世间流传最广、比较容易实现并且高效的方法的是记录每个结点进队次数，超过|V|次表示有负权。
