题目题解代码
题目
古时候有N个城市，编号分为1到N，每两个城市之间有且只有一条路。商人在城市之前做买卖时就会遇到一个问题，那就是每通过一条路，就要支付一定的过路费，这个过路费等于商人身上的金钱数乘以一个不大于1的小数，并且这个小数会因道路的不同而不同。商人想从城市A去到城市B，问最多可以剩下多少钱。 n<=500
题解
很显然，这是一道单源最短路！ Floyd当然简单易行，但是多半会爆几个点 因此我们用dij（这个单词全称不记得了） 此题注意要求留下的路费最多，因此”>”“<”要注意用对 Dij过程： d[i]放从起点s到所有点的路程。 a[u,v]放从u到v的路程 b[i]放从起点s到i点的最短路是否求过 a)初始化： d和a全都弄成很大的数 for i 1——n d[i]=a[s,i]//所有可以从1直接到的点
b)repeat
找一个没有求过最短路且距起点最近的点u
若存在u则用d[u]去更新别的点
i=1——n
d[i]=d[u]+a[u,i](d[i]>d[u]+a[u,i]&i点没有求完最短路)
b[u]标记为求过
until u=0
时间复杂度O(n2)
代码
var
n,x,y,i,j:longint;
a:
array[
0..
500,
0..
500]
of real;
d:
array[
1..
500]
of real;
c:real;
procedure dij;
var
i,u:longint;
min:real;
v:
array[
1..
500]
of boolean;
begin
for i:=
1 to n
do d[i]:=a[x,i];
fillchar(v,sizeof(v),
true);v[x]:=
false;
repeat
min:=
0;u:=
0;
for i:=
1 to n
do
if (d[i]>min)
and v[i]
then
begin min:=d[i];u:=i;
end;
if u>
0 then
begin
for i:=
1 to n
do
if d[u]*a[u,i]>d[i]
then
d[i]:=d[u]*a[u,i];
v[u]:=
false;
end;
until u=
0;
end;
begin
assign(input,
'rate.in');
assign(output,
'rate.out');
reset(input);rewrite(output);
readln(n,x,y);
fillchar(a,sizeof(a),$
7);
for i:=
1 to n
do
begin
for j:=
1 to n
do
begin
read(c);
a[i,j]:=
1-c;
end;
a[i,i]:=a[
0,
0];
end;
dij;
writeln(d[y]:
0:
2);
close(input);close(output);
end.
