用spfa求最长路的pascal代码
发布网友
发布时间：2022-04-24 19:49
共1个回答
热心网友
时间：2023-10-09 02:45
例：Summer的兵力分布在各个星球上，现在需要把他们全部转移到某个星球上。
Summer一共拥有N个星球（1～N），你要把这N个星球上的兵力转到第M个星球上。本来每个星球之间都有星际轨道连接，但Guiolk监视了某些轨道，我们一但走上这些轨道，有可能受到他的攻击。为了安全，Summer不会走被监视的轨道。于是，只有L个星际轨道是被批准通过的。Summer的国防部想统计一下所需的最短路程（即每个星球到第M星球的最短路程总和，单位：M PS：'M'不是米）。
输入格式 Input Format
第一行有三个正整数，N，M，L（分别如题目描述）接下来L行，为被批准通行的轨道。每行有三个整数：a，b，c，表示第a个星球和第b个星球之间的轨道长cM（有重复）。
输出格式 Output Format
如果所有星球上的兵力能全部集中到第M个星球，则输出： 最短路程和+“ M(s) are needed.”如果某个星球的兵力不能到达第M个星球，则输出“Sth wrong.”。
【样例输入1】
5 3 6
1 2 1
1 3 3
2 3 1
4 1 5
4 5 2
5 1 2
【样例输入2】
5 3 4
1 2 1
1 3 3
2 3 1
5 1 2
【样例输出1】
13 M(s) are needed.
【样例输出2】
Sth wrong.
program ysh(input,output);
var
i,n,m,j,l,w,a,b:longint;
sum:qword;
path:array[1..1000,1..1000] of longint; //邻接矩阵
dist:array[1..1000] of qword; //当前各点到源点的最短距离
flag:array[1..1000] of boolean; //标志队列中是否有该点
q:array[1..500000] of longint; //队列
function relax(u,v:longint):boolean; //利用三角不等式进行松弛操作
begin
if (path[u,v]<>maxlongint)and(dist[u]+path[u,v]<dist[v]) then
begin
dist[v]:=dist[u]+path[u,v];
exit(true);
end
else
exit(false);
end;
procere SPFA;
var
t,w,i,v:longint;
begin
t:=1;
w:=1;
q[t]:=m;
flag[m]:=false;
repeat
v:=q[t];
for i:=1 to n do
if relax(v,i) then
if flag[i] then
begin
inc(w);
q[w]:=i;
flag[i]:=false;
end;
flag[q[t]]:=true;
inc(t);
until t>w;
end;
function min(a,b:longint):longint;
begin
if a<b then min:=a
else min:=b;
end;
begin
fillchar(flag,sizeof(flag),true);
for i:=1 to 1000 do dist[i]:=maxlongint;
for i:=1 to 1000 do
for j:=1 to 1000 do
path[i,j]:=maxlongint;
readln(n,m,l);
dist[m]:=0;
for i:=1 to l do
begin
readln(a,b,w);
if path[a,b]=maxlongint then path[a,b]:=w
else path[a,b]:=min(path[a,b],w);
if path[b,a]=maxlongint then path[b,a]:=w
else path[b,a]:=min(path[b,a],w);
end;
SPFA;
sum:=0;
for i:=1 to n do
if dist[i]<>maxlongint then
sum:=sum+dist[i]
else
begin
writeln('Sth wrong.');
exit;
end;
writeln(sum,' M(s) are needed.');
end.
如果是最长路的话只要把各点对之间距离取负，进行SPFA,再把结果变回正就行了。
