| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用PASCAL写的,那位大神看一下,为嘛WA了?program subway;
const
maxn=202;
type
node=record
x,y:longint;
end;
var
map:array[1..maxn,1..maxn]of longint;
dist:array[1..maxn] of longint;
jiedian:array[1..maxn]of node;
f:array[1..maxn]of boolean;
i,j,t,s:integer;
s1,s2:real;
tex:text;
function juli(i,j:integer):longint;
var
x3,y3,x4,y4:longint;
begin
with jiedian[i] do
begin
x3:=x;
y3:=y;
end;
with jiedian[j] do
begin
x4:=x;
y4:=y;
end;
juli:=round(sqrt(sqr(x3-x4)+sqr(y3-y4)));
end;
procedure init;
var
a,b:longint;
begin
assign(tex,'subway.in');
reset(tex);
s1:=2000/3;
s2:=500/3;
fillchar(map,sizeof(map),0);
for i:=1 to 2 do
with jiedian[i] do
read(tex,x,y);
readln(tex);
t:=2;
s:=t;
while not eof(tex) do
begin
read(tex,a,b);
while not eoln(tex) do
begin
inc(t);
with jiedian[t] do
begin
x:=a;
y:=b;
if t<>s+1 then
begin
map[t,t-1]:=round(juli(t,t-1)/s1);
map[t-1,t]:=map[t,t-1];
end;
end;
read(tex,a,b);
end;
s:=t;
readln(tex);
end;
for i:=1 to t do
for j:=1 to t do
if map[i,j]=0 then
begin
map[i,j]:=round(juli(i,j)/s2);
map[j,i]:=map[i,j];
end;
for i:=1 to maxn do
dist[i]:=maxint;
dist[1]:=0;
fillchar(f,sizeof(f),true);
f[1]:=false;
close(tex);
end;
procedure dijkstra(n:integer);
var
min,w:integer;
begin
w:=1;
for i:=1 to n-1 do
begin
min:=maxint;
for j:=1 to n do
if (dist[j]<min)and f[j] then
begin
min:=dist[j];
w:=j;
end;
for j:=1 to n do
if (dist[w]+map[w,j]<dist[j])and f[j] and(map[w,j]<>maxint)
then
dist[j]:=dist[w]+map[w,j];
f[w]:=false;
end;
end;
begin
init;
dijkstra(t);
writeln(dist[2]);
readln;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator