98 条题解
-
0
zsy90943 LV 10 @ 2009-08-20 00:15:21
SPFA王道、、
无视稠密、、无视魔免、、谜团的大太猛了、、
-
0
var h:array[1..10000]of longint;
p:array[1..400]of longint;
dis:array[1..400]of real;
map:array[1..400,1..400]of real;
s,t,c,a,b,i,j,top,x1,x2,x3,x4,y1,y2,y3,y4,head,tail,ti,u:longint;
s12,s23,s13,s14,s24,s34,min:real;
v:array[1..400]of record x,y:longint; end;
function max(a,b,c:real):real;
var maxn:real;
begin
maxn:=0;
if a>maxn then maxn:=a;
if b>maxn then maxn:=b;
if c>maxn then maxn:=c;
max:=maxn;
end;
begin
readln(s,t,c,b);
for i:=1 to s*4 do
for j:=1 to s*4 do
map:=maxlongint;
top:=1;
for i:=1 to s do
begin
readln(x1,y1,x2,y2,x3,y3,ti);
s12:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
s23:=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
s13:=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
if max(s12,s13,s23)=
s12 then begin
x4:=x1+x2-x3;
y4:=y1+y2-y3;
end;
if max(s12,s13,s23)=
s13 then begin
x4:=x1+x3-x2;
y4:=y1+y3-y2;
end;
if max(s12,s13,s23)=
s23 then begin
x4:=x2+x3-x1;
y4:=y2+y3-y1;
end;
s14:=sqrt((x1-x4)*(x1-x4)+(y1-y4)*(y1-y4));
s24:=sqrt((x2-x4)*(x2-x4)+(y2-y4)*(y2-y4));
s34:=sqrt((x4-x3)*(x4-x3)+(y4-y3)*(y4-y3));
v[top+0].x:=x1;v[top+0].y:=y1;
v[top+1].x:=x2;v[top+1].y:=y2;
v[top+2].x:=x3;v[top+2].y:=y3;
v[top+3].x:=x4;v[top+3].y:=y4;
map[top+0,top+0]:=0*ti;map[top+0,top+1]:=s12*ti;map[top+0,top+2]:=s13*ti;map[top+0,top+3]:=s14*ti;
map[top+1,top+0]:=s12*ti;map[top+1,top+1]:=0*ti;map[top+1,top+2]:=s23*ti;map[top+1,top+3]:=s24*ti;
map[top+2,top+0]:=s13*ti;map[top+2,top+1]:=s23*ti;map[top+2,top+2]:=0*ti;map[top+2,top+3]:=s34*ti;
map[top+3,top+0]:=s14*ti;map[top+3,top+1]:=s24*ti;map[top+3,top+2]:=s34*ti;map[top+3,top+3]:=0*ti;
top:=top+4;
end;
top:=top-1;
for i:=1 to top do
for j:=1 to top do
if map=maxlongint then
map:=sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y))*t;
{for i:=1 to top do
begin
for j:=1 to top do
if map=maxlongint then write('Max ') else write(map:5:2,' ');
writeln;
end; }
min:=maxlongint*1.00;
for j:=(c-1)*4+1 to (c-1)*4+4 do
begin
for i:=1 to s*4 do h[i]:=0;
for i:=1 to s*4 do dis[i]:=maxlongint;
for i:=1 to s*4 do p[i]:=0;
a:=j;
dis[a]:=0;
p[a]:=1;
tail:=1;
head:=1;
h[head]:=a;
while head -
0
caojiahao2 LV 9 @ 2009-06-13 18:22:15
type
re=record
x:real;
y:real;
end;
var
g:array[1..400,1..400]of real;
a:array[1..400]of re;
s,t,i,j,k,aa,bb,ti:longint;
min:real;
procedure floyed;
begin
for k:=1 to 4*s do
for i:=1 to 4*s do
for j:=1 to 4*s do
if (g0)and(g>g+g[k,j])then g:=g+g[k,j];
end;
procedure f4;
var
x1,x2,x3,y1,y2,y3,x0,y0,xt,yt:real;
begin
x3:=a.x;x2:=a.x;x1:=a.x;
y3:=a.y;y2:=a.y;y1:=a.y;
{1}
x0:=x3-x1;y0:=y3-y1;
xt:=x2-x1;yt:=y2-y1;
if x0*xt+y0*yt=0 then begin
a[i].x:=x2+x3-x1;
a[i].y:=y2+y3-y1;
exit;
end;
{2}
x0:=x3-x2;y0:=y3-y2;
xt:=x1-x2;yt:=y1-y2;
if x0*xt+y0*yt=0 then begin
a[i].x:=x1+x3-x2;
a[i].y:=y1+y3-y2;
exit;
end;
{3}
x0:=x2-x3;y0:=y2-y3;
xt:=x1-x3;yt:=y1-y3;
if x0*xt+y0*yt=0 then begin
a[i].x:=x1+x2-x3;
a[i].y:=y1+y2-y3;
exit;
end;{使用数学向量思想（a*b=0 则a垂直于b），找垂直点（X,Y）}{向量思想求做标，可导出公式：（X2,Y2）+(X3,Y3)-(X1，Y1) {（X1,Y1）为垂直点}=(X4,Y4)}end;
procedure s4;
var
j,k:longint;
begin
for j:=i-3 to i do
for k:=i-3 to i do
if jk then g[j,k]:=sqrt(sqr(a[j].x-a[k].x)+sqr(a[j].y-a[k].y))*ti;{构建同一城市之间各点钱数}
end;begin
readln(s,t,aa,bb);
for i:=1 to 4*s do
begin
if i mod 4=0 then begin readln(ti);f4;
s4;continue; end;
read(a[i].x,a[i].y);
end;
for i:=1 to 4*s do
for j:=1 to 4*s do
if (ij)and(g=0)then g:=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y))*t;{构建不同城市之间各点钱数}
floyed;
min:=maxlongint*maxlongint;
for i:=4*aa-3 to 4*aa do
for j:=4*bb-3 to 4*bb do
if g -
0
wbx5223166 LV 8 @ 2009-05-25 00:07:43
1.先根据已知的3个点的坐标算出第4个点的坐标（具体在《已知矩形任意三点坐标求矩形第4点坐标.doc》）。主要分两种情况：1：规则矩形（正放），2：非规则矩形（斜放），主要就是计算这种矩形的点
2.计算路费（边权）用邻接矩阵存储
先计算城市内部的，再计算城市之间的。同时因为题目要求为a城市任意一点出发，故a城市内所有点值为边权0
3.再用dijkstra计算单源最短路径。
注：因为a城市各边权值为0，所以只用做一遍，不会影响值。根据dijkstra性质先确定b城市的点一定是a到b最短的，所以在找到第一个b城市的点后跳出另：请大家支持一下，如果看到我这篇题解有思路的话请告知我一声！！谢谢（回贴、密我）
-
0
zhengfangyi LV 10 @ 2009-05-12 18:36:32
不看题害死人呀!
-
0
lijian3256 LV 10 @ 2009-04-10 14:35:36
判断矩形写的有点猥琐。。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：0ms哦~~不~~~ 又是错了一个点
#include
#include
#include
using namespace std;
int n,cost,start,end;
double f[101][5][101][5],ans;
struct {
int x[5],y[5];
int til;
}map[101];
double dis(int x1,int y1,int x2,int y2){
return sqrt(double((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}
void init(){
scanf("%d%d%d%d",&n,&cost,&start,&end);
int i;
double a,b,c;
for(i=1;i=b&&a>=c){
map[i].x[4]=map[i].x[1]+map[i].x[2]-map[i].x[3];
map[i].y[4]=map[i].y[1]+map[i].y[2]-map[i].y[3];
}
else if(b>=a&&b>=c){
map[i].x[4]=map[i].x[1]+map[i].x[3]-map[i].x[2];
map[i].y[4]=map[i].y[1]+map[i].y[3]-map[i].y[2];
}
else {
map[i].x[4]=map[i].x[2]+map[i].x[3]-map[i].x[1];
map[i].y[4]=map[i].y[2]+map[i].y[3]-map[i].y[1];
}
}
}
void work(){
int i,j,k,l,r,h;
for(i=1;i -
0
Prince Frost LV 10 @ 2009-03-12 21:38:16
这题数据太弱了吧？Floyd竟然过了，还是0ms，Orz……
-
0
gnaggnoyil LV 10 @ 2009-01-31 21:51:01
HEAP+DIJKSTRA!稠密图王道!!!
(我要吐血了!!!) -
0
zkh19928227 LV 8 @ 2008-11-07 18:45:44
program car;
var
s,tt,a,b,i,j,n,o,q,start,zx,zy:longint;
k:array[1..3] of real;
lk,lb:array[1..3] of real;
x,y:array[1..4,1..100] of real;
w:array[1..400,1..400] of real;
tell:array[1..400] of 0..1;
t:array[1..100] of longint;
min:array[1..400] of real;
m,kk,max:real;
begin
readln(s,tt,a,b);
for i:=1 to s do readln(x[1,i],y[1,i],x[2,i],y[2,i],x[3,i],y[3,i],t[i]);
for i:=1 to s do
begin
k[3]:=sqrt(sqr(abs(x[1,i]-x[2,i]))+sqr(abs(y[1,i]-y[2,i])));
k[1]:=sqrt(sqr(abs(x[2,i]-x[3,i]))+sqr(abs(y[2,i]-y[3,i])));
k[2]:=sqrt(sqr(abs(x[1,i]-x[3,i]))+sqr(abs(y[1,i]-y[3,i])));
max:=0;
for j:=1 to 3 do if k[j]>max then begin max:=k[j]; n:=j; end;
o:=0; zx:=0; zy:=0;
for j:=1 to 3 do
if jn then
begin
x[4,i]:=x[4,i]+x[j,i];
y[4,i]:=y[4,i]+y[j,i];
end;
x[4,i]:=x[4,i]-x[n,i]; y[4,i]:=y[4,i]-y[n,i];
end;
for i:=1 to s do
begin
for j:=1 to 3 do
for o:=j+1 to 4 do
w[4*i-4+j,4*i-4+o]:=sqrt(sqr(abs(x[j,i]-x[o,i]))+sqr(abs(y[j,i]-y[o,i])))*t[i];
for j:=1 to 4 do
for q:=i+1 to s do
for o:=1 to 4 do
begin
w[4*i-4+j,4*q-4+o]:=sqrt(sqr(abs(x[j,i]-x[o,q]))+sqr(abs(y[j,i]-y[o,q])))*tt;
end;
end;
n:=4*s;
for i:=2 to n do for j:=i-1 downto 1 do w:=w[j,i];
m:=99999999;
for i:=1 to 4 do
begin
fillchar(tell,sizeof(tell),0);
tell[4*a-4+i]:=1; start:=4*a-4+i;
for j:=1 to n do min[j]:=99999999; min[4*a-4+i]:=0;
while (tell[4*b-3]=0) and (tell[4*b-2]=0) and (tell[4*b-1]=0) and (tell[4*b]=0) do
begin
for j:=1 to n do if (tell[j]=0) and (w[start,j]+min[start] -
0
const
longest=1e18;
min=1e-6;
type
tpoint=record
x,y:extended;
end;
var
nod:array[1..400]of tpoint;
rail:array[1..100]of extended;
n,s,a,b,task:integer;
air:extended;
function dis(a,b:tpoint):extended;
begin
dis:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
end;
procedure initalize;
var
i,p:integer;
d,d1:extended;
begin
readln(s,air,a,b);
for i:=1 to s do
begin
readln(nod.x,nod.y,
nod.x,nod.y,
nod.x,nod.y,rail[i]);
p:=1;
d:=dis(nod,nod);
d1:=dis(nod,nod);
if d1>d then
begin
d:=d1;
p:=2;
end;
d1:=dis(nod,nod);
if d1>d then
begin
d:=d1;
p:=3;
end;
case p of
1:begin
nod.x:=nod.x+nod.x-nod.x;
nod.y:=nod.y+nod.y-nod.y;
end;
2:begin
nod.x:=nod.x+nod.x-nod.x;
nod.y:=nod.x+nod.y-nod.y;
end;
3:begin
nod.x:=nod.x+nod.x-nod.x;
nod.y:=nod.y+nod.y-nod.y;
end;
end;
end;
end;
procedure solve;
var
i,j,k:integer;
v:array[1..400]of 0..1;
short:array[1..400]of extended;
c,d:extended;
begin
fillchar(v,sizeof(V),0);
for i:=1 to s*4do short[i]:=longest;
for i:=(a-1)*4+1 to (a-1)*4+4 do
begin
v[i]:=1;short[i]:=0;
end;
while true do
begin
d:=longest;
k:=0;
for i:=1 to s*4 do
if(v[i]=1)and(short[i]-dmin then
begin
short[i]:=short[k]+d*air;v[i]:=1;
end;
end;
for i:=(k-1)div 4*4+5 to s*4 do
begin
d:=dis(nod[k],nod[i]);
if short[i]-short[k]-d*air>min then
begin
short[i]:=short[k]+d*air;v[i]:=1;
end;
end;
c:=rail[(k-1)div 4+1];
for i:=(k-1)div 4*4+1 to (k-1)div 4*4+4 do
if ik then
begin
d:=dis(nod[k],nod[i]);
if short[i]-short[k]-d*c>min then
begin
short[i]:=short[k]+d*c;v[i]:=1;
end;
end;
v[k]:=0;
end;
c:=longest;
for i:=(b-1)*4+1 to (b-1)*4+4 do
if c-short[i]>min then
c:=short[i];
writeln(c:0:2);
end;
begin
initalize;
solve;
end.
zsy90943
LV 10
@ 2009-08-20 00:15:21
