说说我的方法;
开A,B数组,初始化一样储存权值
A求最短路,而B不作修改,求a[i,j]+b[i,k]+b[k,j]的min(k作为中转)
min就出来了。
不明白,某人的解释是,去时是a[i,j]最短,回时因为有k作中转,b[i,k]+b[k,j],所以不会从原路返回。
floyed时间是有些简陋,但由于此题太水、、
var a,b:array[0..1000,0..1000]of longint;
n,i,j,s,x,y,z,k,min:longint;
begin
readln(n,s);
for i:=1 to n do for j:=1 to n do begin a[i,j]:=99999; b[i,j]:=99999; end;
for i:=1 to s do
begin
readln(x,y,z); a[x,y]:=z; a[y,x]:=z; b[x,y]:=z; b[y,x]:=z;
end;
for i:=1 to n do begin a[i,i]:=0; b[i,i]:=0; end;
min:=maxlongint;
for k:=1 to n do
begin
for i:=1 to n do
for j:=1 to n do
if (a[i,k]<>0)and(a[k,j]<>0)and(a[i,j]<>0) then
if (a[i,j]+b[i,k]+b[k,j])<min then min:=a[i,j]+b[i,k]+b[k,j];
for i:=1 to n do
for j:=1 to n do
if (a[i,k]<>0)and(a[k,j]<>0)and(a[i,j]<>0) then
if a[i,k]+a[k,j]<a[i,j] then a[i,j]:=a[i,k]+a[k,j];
end;
if min<9999 then write(min) else write('He will never come back.');
end.
k此时没有作为中转点进行松弛操作,因此a[i,j]中一定没有k,保证不出现一条路走两边,我要分,不懂再问