[題目來源]：NOIP2001提高組T4

[關(guān)鍵字]：最短路徑

[題目大意]：給定平面直角若干個矩形，計算(可經(jīng)過其他矩形)兩個矩形任意頂點間的最短路程費用。

//============================================================================================================

[分析]：其實題目本事沒有太大的難點，只需要對每兩個點進行連邊(其實不用連知道坐標(biāo)后現(xiàn)求兩點間距離)然后求最短路即可。關(guān)鍵是如何知道給定三個頂點的矩形的另一個頂點。

公式：(x1,y1)(x2,y2)(x3,y3)為三個頂點坐標(biāo)，如果(x1-x2)*(x3-x1)+(y1-y2)*(y3-y1)=0則x4=x2+x3-x1 y4=y2+y3-y1。只要循環(huán)直到找到第四個點即可，具體實現(xiàn)可看代碼。

[代碼]：

View Code

program project1;

type

rec = record

x, y, c: longint;

end;

var

n, tot, costf, st, ed, tc: longint;

pos: array[0..2000] of rec;

x, y: array[1..4] of longint;

costt: array[0..200] of longint;

b: array[0..200] of boolean;

d: array[0..100] of real;

procedure init;

var

i, j, k: longint;

begin

readln(n,costf,st,ed);

for i := 1 to n do

begin

readln(x[1],y[1],x[2],y[2],x[3],y[3],costt[i]);

for j := 1 to 3 do

for k := 1 to 3 do

if j <> k then

if (x[j]-x[k])*(x[6-k-j]-x[j])+(y[j]-y[k])*(y[6-k-j]-y[j]) = 0 then

begin

x[4] := x[k]+x[6-k-j]-x[j];

y[4] := y[k]+y[6-k-j]-y[j];

end;

for j := 1 to 4 do

begin

inc(tot);

pos[tot].x := x[j];

pos[tot].y := y[j];

pos[tot].c := i;

end;

end;

//for i := 1 to tot do writeln(pos[i].x,' ',pos[i].y,' ',pos[i].c);

end;

function dis(x, y: longint):real;

begin

dis := sqrt(sqr(pos[x].x-pos[y].x)+sqr(pos[x].y-pos[y].y));

if pos[x].c = pos[y].c then

dis := dis*costt[pos[x].c]

else dis := dis*costf;

end;

function dij(st: longint):real;

var

i, j, p: longint;

min: real;

begin

fillchar(b,sizeof(b),false);

fillchar(d,sizeof(d),100);

d[st] := 0;

for i := 1 to tot do

begin

min := 1e38;

for j := 1 to tot do

if (not b[j]) and (d[j] < min) then

begin

min := d[j];

p := j;

end;

b[p] := true;

for j := 1 to tot do

if not b[j] then

if d[j] > d[p]+dis(p,j) then d[j] := d[p]+dis(p,j);

end;

dij := 1e38;

for i := 1 to tot do

begin

if pos[i].c = ed then

for j := 0 to 3 do

if d[i+j] < dij then dij := d[i+j];

if pos[i].c = ed then break;

end;

end;

procedure work;

var

i, j: longint;

min, temp: real;

begin

min := 1e38;

for i := 1 to tot do

begin

if pos[i].c = st then

for j := 0 to 3 do

begin

temp := dij(i+j);

if temp < min then min := temp;

end;

if pos[i].c = st then break;

end;

writeln(min:0:1);

end;

begin

assign(input,'d:\in.txt');reset(input);

assign(output,'d:\out.txt');rewrite(output);

readln(tc);

while tc > 0 do

begin

init;

work;

dec(tc);

end;

close(input);

close(output);

end.

總結(jié)

以上是生活随笔為你收集整理的init tarray 太大_[NOIP 2001提高组T4]Car的旅行路线的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。