PersonalCorpus 版 (精华区)

寄信人: sino (蚱蜢舟)
标  题: 1205
发信站: 哈工大紫丁香 (2002年03月23日10:33:43 星期六)
来  源: mtlab4.hit.edu.cn 

171109 02:35:19 23 Mar 2002
Bozhang,HIT,P.R.China 1205 Pascal Accepted 0.811 sec 299K


171108 02:34:31 23 Mar 2002
Bozhang,HIT,P.R.China 1205 Pascal Accepted 0.28 sec 463K


var
    pp:array[0..201,1..2] of real;
    dl:array[0..201,0..201] of real;
    path:array[0..201] of byte;
    res:array[1..200] of byte;
    sp1,sp2:real;
    i,j,k,n:integer;
procedure Dijkstra;
var
    mark:array[0..201] of boolean;
    best:real;
    best_i,best_j,i,j:integer;
begin
    fillchar(mark,sizeof(mark),0); mark[0]:=true;
    repeat
        best:=-1;
        for i:=0 to n+1 do if mark[i] then
            for j:=0 to n+1 do if (not mark[j]) and (dl[i,j]>=0) then
                if (best<0) or (dl[0,i]+dl[i,j]<best) then begin
                    best:=dl[0,i]+dl[i,j];
                    best_j:=j;  best_i:=i;
                end;
        if best>=0 then begin
            dl[0,best_j]:=best;
            dl[best_j,0]:=best;
            mark[best_j]:=true;
            path[best_j]:=best_i;
            if best_j=n+1 then exit;
        end;
    until best=-1;
end;
begin
    readln(sp1,sp2);
    readln(n); for i:=1 to n do readln(pp[i,1],pp[i,2]);
    fillchar(path,sizeof(path),0);
    for i:=0 to n+1 do for j:=0 to n+1 do dl[i,j]:=0;
    readln(j,k);
    while (j<>0) and (k<>0) do begin
        dl[k,j]:=sqrt(sqr(pp[k,1]-pp[j,1])+sqr(pp[k,2]-pp[j,2]))/sp2;
        dl[j,k]:=dl[k,j];
        readln(j,k);
    end;
    readln(pp[0,1],pp[0,2]);
    readln(pp[n+1,1],pp[n+1,2]);
    for i:=0 to n+1 do
        for j:=i to n+1 do if dl[i,j]=0 then begin
            dl[i,j]:=sqrt(sqr(pp[i,1]-pp[j,1])+sqr(pp[i,2]-pp[j,2]))/sp1;
            dl[j,i]:=dl[i,j];
        end;
    Dijkstra;
    writeln(dl[0,n+1]:0:7);
    k:=0;
    j:=n+1;
    while path[j]<>0 do begin
        inc(k); res[k]:=path[j]; j:=path[j];
    end;

    write(k,' ');
    for i:=k downto 1 do write(res[i],' ');
    writeln;
end.


--
千 但 此 月 人 别 何 不 照 低 转 何 起 高 又 我 今 不 把 明 
里 愿 事 有 有 时 事 应 无 绮 朱 似 舞 处 恐 欲 夕 知 酒 月 
共 人 古 阴 悲 圆 长 有 眠 户 阁 在 弄 不 琼 乘 是 天 问 几 
婵 长 难 晴 欢    向 恨          人 清 胜 楼 风 何 上 青 时 
娟 久 全 圆 离                   间 影 寒 玉 归 年 宫 天 有 
         缺 合                            宇 去    阙       

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]