首页 > 代码库 > CodeVS 1041 Car的旅行路线 Pascal
CodeVS 1041 Car的旅行路线 Pascal
题目大意：
题解：很明显建图之后Floyd一下即可。
首先根据勾股定理，可以求出两点之间的距离为√(x1-x2)2(y1-y2)2，然后根据长方形内的三个点求出第四个点，也是根据勾股定理，先求出三个点之中每两个点之间的距离，即b1=√(x1-x2)2(y1-y2)2,b2=√(x1-x3)2(y1-y3)2,b3=√(x2-x3)2(y2-y3)2,如果最长边为b1，则第四个点的坐标为(x1+x2-x3,y1+y2-y3)；如果最长边为b2，则第四个点的坐标为(x1-x2+x3,y1-y2+y3)；如果最长边为b3，则第四个点的坐标为(-x1+x2+x3,-y1+y2+y3)。
把第四给点搞定之后，再在城市中四个点每两个点之间建一条边，权值为走公路所用花费。接下来在全部城市读入完毕之后，枚举每两个城市之间的每两个点，建一条边，权值为航班花费。
这样就建图完成了，接下来就进行Floyd。
最后枚举起点与终点的每两个点，求出最小花费即为答案。
var n,s,t,a,b,i,j,k,i1,j1,x4,y4,he,l:longint;
var ans:double;
var d:array[0..500,0..500] of double;
var x,y:array[0..100,1..4] of longint;
var b1:array[1..100] of longint;
function min(a,b:double):double;
begin
if a<b then exit(a);exit(b);
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure max(var a,b,c:longint);
var t:longint;
begin
if a<c then swap(a,c);
if a<b then swap(a,b);
if b<c then swap(b,c);
end;
function hh(x,y,x1,y1:longint):double;
begin
exit(sqrt(sqr(x-x1)+sqr(y-y1))*he);
end;
procedure xy(x1,y1,x2,y2,x3,y3:longint);
var b1,b2,b3:double;
begin
he:=1;
b1:=hh(x1,y1,x2,y2);b2:=hh(x1,y1,x3,y3);b3:=hh(x2,y2,x3,y3);
if (b1>=b2) and (b1>=b3) then
begin x[j,4]:=abs(x1+x2-x3);y[j,4]:=abs(y1+y2-y3);end
else if (b2>=b1) and (b2>=b3) then
begin x[j,4]:=abs(x1+x3-x2);y[j,4]:=abs(y1+y3-y2);end else
begin x[j,4]:=abs(x2+x3-x1);y[j,4]:=abs(y2+y3-y1);end;
end;
begin
read(n);
for i1:=1 to n do
begin
for j:=1 to 500 do for k:=1 to 500 do d[j,k]:=0;
fillchar(b1,sizeof(b1),0);
fillchar(x,sizeof(x),0);fillchar(y,sizeof(y),0);
read(s,t,a,b);ans:=maxlongint;
for j:=1 to s do
begin
for k:=1 to 3 do read(x[j,k],y[j,k]);read(b1[j]);
xy(x[j,1],y[j,1],x[j,2],y[j,2],x[j,3],y[j,3]);
he:=b1[j];
for k:=3 downto 1 do
for j1:=k-1 downto 0 do
begin
d[4*j-k,4*j-j1]:=hh(x[j,4-k],y[j,4-k],x[j,4-j1],y[j,4-j1]);
d[4*j-j1,4*j-k]:=d[4*j-k,4*j-j1];
end;
end;
he:=t;
for j:=1 to s do
for k:=j+1 to s do
for l:=3 downto 0 do
for j1:=3 downto 0 do
begin
d[4*j-l,4*k-j1]:=hh(x[j,4-l],y[j,4-l],x[k,4-j1],y[k,4-j1]);
d[4*k-j1,4*j-l]:=d[4*j-l,4*k-j1];
end;
for k:=1 to 4*s do
for i:=1 to 4*s do
for j:=1 to 4*s do
if d[i,k]+d[k,j]<d[i,j] then
d[i,j]:=d[i,k]+d[k,j];
for i:=3 downto 0 do
for j:=3 downto 0 do
begin
ans:=min(d[a*4-i,b*4-j],ans);
end;
writeln(ans:0:1);
end;
end.
感谢阅读！
CodeVS 1041 Car的旅行路线 Pascal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。