讨论 / AC了,但还是不懂,求解释
神经病有所好转 2011-11-02 07:25:00
点我顶贴 收藏 删除
用最原始的floyed,过了,但还是不明白为什么可以。

说说我的方法;

开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.

#1 cszqwe@2011-02-12 17:53:00
回复 删除
A求最短路,而B不作修改,求a[i,j]+b[i,k]+b[k,j]的min(k作为中转)

k此时没有作为中转点进行松弛操作,因此a[i,j]中一定没有k,保证不出现一条路走两边,我要分,不懂再问

#2 神经病有所好转@2011-02-23 02:14:00
回复 删除
求神牛解释、

不懂ls

#3 abccbazj@2011-02-25 01:57:00
回复 删除
上层的循环是判断出经过最短路的计算后是否有环,

下层的循环就是进行最短的路径。

#4 abcdefg555@2011-11-02 07:25:00
回复 删除
floyed求最小环

很简单的嘛!

第一个是保证不会经过k,i,i,k,能形成的最小环

第二个循环不解释

#5 abcdefg555@2011-11-02 07:25:00
回复 删除
floyed求最小环

很简单的嘛!

第一个是保证不会经过k,i,i,k,能形成的最小环

第二个循环不解释

查看更多回复
提交回复