P1027 Car的旅行路线 - 华师一附中OI组

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const int inf=2147483647;
const double eps=0.001;
const int mm=500*4*2; //算500个点这样足够了
const int mn=500;
int n,s,t,A,B;
double xi1,xi2,xi3,xi4,yi1,yi2,yi3,yi4;
double T,w;
double cityx[mn],cityy[mn];//城市四个点
int nxt[mm],ev[mm],me;
double ew[mm];
int vist[mn],nbs[mn];
double dist[mn];
double sqr(double x){return x*x;}
double d(double x1,double y1,double x2,double y2)
{ return sqrt(sqr(x1-x2)+sqr(y1-y2));}
void calc4(double x1,double y1,double x2,double y2,double x3,double y3,double & x4,double & y4)
{
double t12,t13,t23;
t12=d(x1,y1,x2,y2);
t13=d(x1,y1,x3,y3);
t23=d(x3,y3,x2,y2);///注意判断的技巧，实数一般不直接比较相等
if (abs(sqr(t12)+sqr(t13)-sqr(t23))<eps) x4=x2+x3-x1,y4=y2+y3-y1;
else if (abs(sqr(t12)+sqr(t23)-sqr(t13))<eps) x4=x1+x3-x2,y4=y1+y3-y2;
else if (abs(sqr(t13)+sqr(t23)-sqr(t12))<eps) x4=x1+x2-x3,y4=y1+y2-y3;
}
int getmin()
{
int m,k,i;
m=inf;
k=0; ///起点，无路可找的时候就返回0。此题全连通当然不会出现
///for (i=1;i<=n;i++) cout<<dist[i]<<' '; cout<<endl;
for (i=1; i<=4*s+1; i++)
if (!vist[i]) if (dist[i]<m) {m=dist[i];k=i;}
return k;
}
void dijkstra(int src,int dst)
{
int i,j,u,v;
for(i=1; i<=4*s+1; i++) { dist[i]=inf;vist[i]=0;};
dist[src]=0;
while(!vist[dst])
{
u=getmin();vist[u]=1;
for(j=nbs[u]; j!=0; j=nxt[j])
{
v=ev[j];
if(!vist[v]&&dist[u]+ew[j]<dist[v]) dist[v]=dist[u]+ew[j];
}
}
}
void checktable()///检查用
{
for (int ii=0; ii<=4*s+1; ii++)
{
cout<<endl<<ii<<' '<<nbs[ii]<<' '<<endl;
for(int jj=nbs[ii]; jj!=0; jj=nxt[jj]) cout<<setw(8)<<jj<<' ';
cout<<endl;
for(int jj=nbs[ii]; jj!=0; jj=nxt[jj]) cout<<setw(8)<<ev[jj]<<' ';
cout<<endl;
for(int jj=nbs[ii]; jj!=0; jj=nxt[jj]) cout<<setw(8)<<ew[jj]<<' ';
cout<<endl;
}
}
void init()///初始化
{
int i;///好像其实某些也可以不用清零的
for(i=0; i<=mm-1; i++)nxt[mm]=ev[mm]=ew[mm]=0;
for(i=0; i<=mn-1; i++)nbs[mn]=0;
me=0;
}
int main()
{
cin>>n;while (n--) ///巧妙的少设一个变量
{
init(); ///清邻接表，最短路表等
cin>>s>>t>>A>>B;
for(int is=1; is<=s; is++) ///is表示第几个城市
{
cin>>xi1>>yi1>>xi2>>yi2>>xi3>>yi3>>T;
///求出第四个机场的位置
calc4(xi1,yi1,xi2,yi2,xi3,yi3,xi4,yi4);
///保存市内交通到邻接表
cityx[4*is-3]=xi1;
cityx[4*is-2]=xi2;
cityx[4*is-1]=xi3;
cityx[4*is-0]=xi4;
cityy[4*is-3]=yi1;
cityy[4*is-2]=yi2;
cityy[4*is-1]=yi3;
cityy[4*is-0]=yi4;
for (int ii=4*is-3; ii<=4*is-1; ii++)
for (int jj=ii+1; jj<=4*is; jj++)
{
w=T*d(cityx[ii],cityy[ii],cityx[jj],cityy[jj]);
nxt[++me]=nbs[ii];
nbs[ii]=me;
ev[me]=jj;
ew[me]=w;
nxt[++me]=nbs[jj];
nbs[jj]=me;
ev[me]=ii;
ew[me]=w;
}
///计算和前面的所有城市的机场交通并保存
for (int ii=1; ii<=4*is-4; ii++)
for (int jj=4*is-3; jj<=4*is; jj++)
{
w=t*d(cityx[ii],cityy[ii],cityx[jj],cityy[jj]);
nxt[++me]=nbs[ii];
nbs[ii]=me;
ev[me]=jj;
ew[me]=w;
nxt[++me]=nbs[jj];
nbs[jj]=me;
ev[me]=ii;
ew[me]=w;
}
///加入起点和终点
for (int jj=4*A-3; jj<=4*A; jj++)
{
w=0;
nxt[++me]=nbs[0];
nbs[0]=me;
ev[me]=jj;
ew[me]=w;
}
for (int jj=4*B-3; jj<=4*B; jj++)
{
w=0;
nxt[++me]=nbs[jj];
nbs[jj]=me;
ev[me]=4*s+1;
ew[me]=w;
}
}
///输出城市的四个点坐标检查
/*for (int ii=1; ii<=s; ii++)
{
cout<<endl<<ii<<endl;
for (int jj=4*ii-3; jj<=4*ii; jj++) cout<<cityx[jj]<<' '<<cityy[jj]<<endl;
}
///输出邻接表检查
checktable();
*/
dijkstra(0,4*s+1);
cout<<fixed<<setprecision(1)<<dist[4*s+1];
}
return 0;
}

复制代码